Can a classical supercomputer solve a large Max-Cut Problem? The Fugaku is the most powerful computer. Its performance is 442,010 TFlop/s. That number does not mean much to a layman like me. I want to know how fast it can solve a hard problem. For example, can it solve the Max-Cut Problem of 1,000 vertices in minutes, hours,...,years?
By the way, what is the best record of solving the Max-Cut Problem by any classical computers?
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).