4 ms·
(unless P=NP in which case all non-trivial problems in P are also NP-Complete)
by CaptainNegative 4y ago
(unless P=NP in which case all non-trivial problems in P are also NP-Complete)
- yuuu 4y agoZING!
- adgjlsfhk1 4y agoI'm pretty sure this is false (unless you have a very odd definition of trivial).
- CaptainNegative 4y agoNothing 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.
- adgjlsfhk1 4y agoOops. I'm used to thinking of polynomial reductions as "cheap reductions" which given hindsight is obviously misleading when P=NP.