3 ms·
> Proving an inequality is "easy", because only requires a single counterexample: Proving an equality isn't exactly "harder" (no NP-hard pun intended) - all yo
by chimeracoder 14y ago
> Proving an inequality is "easy", because only requires a single counterexample:
Proving an equality isn't exactly "harder" (no NP-hard pun intended) - all you have to do is show that a single NP-complete problem can be reduced to a problem within P in polynomial time.
- PeterBB 14y agoThat's true in this case, but only because we have other results showing that various problems are NP-complete.