No -- as another commenter pointed out, max-cut is (almost certainly) a much harder problem. Specifically, there are algorithms that guarantee to solve every m

No -- as another commenter pointed out, max-cut is (almost certainly) a much harder problem. Specifically, there are algorithms that guarantee to solve every min-cut problem instance in time polynomial in the size of the problem (CS theorists call such algorithms "efficient"), while max-cut is an NP-complete problem. All NP-complete problems are "as hard as each other", and while no one has yet proven that they all take exponential time to solve, the brightest minds in CS have been searching for a faster algorithm for 40 years without success so far. Most people take that lack of progress as evidence that these problems really are hard. The most famous NP-complete problem is probably the Travelling Salesman Problem. Another interesting one (because it seems like it "shouldn't be that hard") is Partition: Given a set of integers, can you partition them into two halves with equal sum?