principleMajor
Does a polynomial solution for an NP-complete problem that can only be implemented for small N *still* imply P=NP?
Viewed 0 times
problemcanimplypolynomialimplementedcompletethatfordoessmall
Problem
Basic sanity check on NP-complete solutions:
Suppose there was a polynomial time solution for an NP-complete problem,
but the size of NP-complete problems that could be solved is still
relatively small (i.e. N = 32-64) due to limits in technology.
Would this show that P = NP? Or would this be more like the
pseudo-solution that the unary subset sum is in P?
Suppose there was a polynomial time solution for an NP-complete problem,
but the size of NP-complete problems that could be solved is still
relatively small (i.e. N = 32-64) due to limits in technology.
Would this show that P = NP? Or would this be more like the
pseudo-solution that the unary subset sum is in P?
Solution
If you mean that the polynomial-time algorithm only works for inputs up to some fixed size, it shows nothing at all. Any problem at all (even if it's undecidable, let alone NP-complete) becomes a finite language when restricted to instances of constant size. All finite languages can be decided in constant time.
If you mean that the polynomial-time algorithm works for all inputs but it's still so inefficient that current computers can only run it on small instances then, sure, that would prove that P$\,=\,$NP. The idea that "polynomial" means "efficiently and effectively solvable" is just a short-hand. The actual definitions of P and NP don't depend on that short-hand.
If you mean that the polynomial-time algorithm works for all inputs but it's still so inefficient that current computers can only run it on small instances then, sure, that would prove that P$\,=\,$NP. The idea that "polynomial" means "efficiently and effectively solvable" is just a short-hand. The actual definitions of P and NP don't depend on that short-hand.
Context
StackExchange Computer Science Q#59412, answer score: 29
Revisions (0)
No revisions yet.