I remember learning an amazing randomized algorithm for max cut. If you pick edges at random 50/50 to be cut, you get a 2-approximation to the optimal solution. That is it's no more than twice as bad.

Really not bad for "just guess".

The first approximation algorithm, invented by Erdős. The best known by Goemans and Williamson achieves about 0.868 (IIRC) approximation, and is a thing of beauty as well.

A rare example of a constant-factor approximation algorithm with a constant that's... actually useful in practice.

No, maximum cut is a significantly harder problem. Minimum cut, on the other hand, is equivalent to maximum flow: https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem

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?

Invert all edge weights.

This would prove P = NP. The catch being that only positive weights are allowed.