So we have this web of interconnected problems which are all at least as hard as each other. None of them is known to be in P, but none of them are proven *not* to be in P. If any one of them were in P, it would have to be that P=NP.
Two other points of clarification. NP stands for "non-deterministic polynomial," not "non-polynomial" as a lot of people assume. A problem is in NP if or can be solved in polynomial time when you're allowed to make one polynomial-sized "guess" that's guaranteed to be right.
Or another way to think of NP is that, if someone says they have a solution to a particular instance of the problem, you can check their answer in polynomial time. (Their answer is the "guess.")
And lastly, for all of this, "polynomial" means "eventually bounded by a polynomial of the input size." So even if it's true that P=NP, there's no guarantee it's *useful.*
E.g., it may be that the runtimes of NP problems are bounded by polynomials with terms like n^100 or 10^(10^100). Technically polynomial, but so large a bound that the "efficient" solution might never find a solution in the lifetime of the universe.
Comments