  Dynamical Ising machines are actively investigated from the perspective of
finding efficient heuristics for NP-hard optimization problems. However, the
existing data demonstrate super-polynomial scaling of the running time with the
system size, which is incompatible with large NP-hard problems. We show that
oscillator networks implementing the Kuramoto model of synchronization are
capable of demonstrating polynomial scaling. The dynamics of these networks is
related to the semidefinite programming relaxation of the Ising model ground
state problem. Consequently, such networks, as we numerically demonstrate, are
capable of producing the best possible approximation in polynomial time. To
reach such performance, however, the reconstruction of the binary Ising state
(rounding) must be specially addressed. We demonstrate that commonly
implemented forced collapse to a close-to-Ising state may diminish the
computational capabilities up to their complete invalidation. Therefore,
consistent treatment of rounding may cardinally improve various operation
metrics of already existing and upcoming dynamical Ising machines.
