Reweighted Weighted Matching is my new algorithm for computing a ground state of an Ising spin glass, resp. (equivalently) a maximum graph cut, resp. a MAP state of a pariwise binary Markov random field. It uses a Langrangian relaxation to leverage the duality between Ising states and perfect matchings from planar to nonplanar graphs, where the ground state problem is known to be NP-hard and non-approximable. Nonetheless my algorithm always runs in polynomial time, and is much faster and scales to much larger graphs than the best previously known methods. The question of P=NP is preserved by the possibility of our algorithm returning a "don't know" answer, though this has never yet been observed in best-practice use. This strongly suggests that the max cut problem is polynomial in the average and perhaps even smoothed worst case, on graphs where it is worst-case NP-hard.