Hacker News new | ask | show | jobs
by xiaodai 1521 days ago
Np=p
2 comments

To be clear, max-flow/min-cost flow is not NP-Complete.
(unless P=NP in which case all non-trivial problems in P are also NP-Complete)
I'm pretty sure this is false (unless you have a very odd definition of trivial).
Nothing funky. "Non-trivial" here is used in the same way as in Rice's theorem, i.e. the language is neither 0* (the program always returns false) nor 1* (the program always returns true).

It's ridiculously simple to show that if P=NP, then every nontrivial language A is NP-hard. For given a language B in NP, one can poly-time reduce B to A by writing a program to straight-up decide B in polynomial time, and then map true instances of B to a pre-determined true instance of A, and false instances of B to a pre-determined false instance of A. In particular, this means that any language in P is in both NP and NP-hard, and thus NP-complete.

Oops. I'm used to thinking of polynomial reductions as "cheap reductions" which given hindsight is obviously misleading when P=NP.
ZING!
No, most likely not, sadly.