Can a classical supercomputer solve a large Max-Cut Problem?
It's not that straightforward. NP-hardness means worst case intractability. This means that there are plenty of easy instances of Max-Cut with a huge number of vertices (i.e. much more than just one thousand), but also rather tiny instances that are extremely hard in practice. So you can't measure hardness by the size of an instance.
If you want to see examples &amp; runtimes, have a look at the results from the yearly competitions around the Boolean satisfiability problem (SAT).