principleMinor
Are there problems in $P$, long suspected to be $NPC$ (or $NPI$)?
Viewed 0 times
suspectedarenpclongproblemsnpithere
Problem
One of the most compelling arguments people cite for believing $P \ne NP$ is that there are many problems of both theoretical and practical significance for which an efficient solution has eluded many intelligent people's concerted efforts for a very long period of time.
The strength of this argument seems to depend on the precise details of the history of algorithmic discovery$^1$. Consider these two extremes:
So are there any problems which were, for a significant amount of time, suspected to be $NPC$ (or $NPI$) and were later finally proven to be in $P$?
$^1$ with which I'm not familiar
The strength of this argument seems to depend on the precise details of the history of algorithmic discovery$^1$. Consider these two extremes:
- if for all problems now known to be in $P$, a deterministic polynomial algorithm was found without much difficulty soon after someone started studying them, this seems compelling evidence that there simply isn't a deterministic polynomial algorithm to solve $SAT$
- if there are a lot of problems now known to be in $P$ for which many attempts to find a deterministic polynomial algorithm failed for many years, this seems to weaken the argument
So are there any problems which were, for a significant amount of time, suspected to be $NPC$ (or $NPI$) and were later finally proven to be in $P$?
$^1$ with which I'm not familiar
Solution
There are a few problems where we were not sure whether they were in P or not, and then later were found to be in P. Not a lot, but a few.
Probably the leading example is primality testing. Even before it was known to be in P, I think many computer scientists still suspected that it was likely to be in P (based on an expectation that BPP = P), but a proof seemed well out of our reach.
Linear programming is another problem where it took a little while to find a polynomial-time algorithm. For a little while, we knew about the simplex algorithm, which was often efficient in practice but which is not polynomial-time in the worst case. Then Khachiyan proved that the ellipsoid algorithm runs in polynomial time, leading to new methods for solving linear programming problems.
There are some problems where a polynomial-time algorithm is not entirely trivial to find. For example, maximum matching or 2SAT are two examples where a new undergrad who looks at the problem might not immediately see a polynomial-time algorithm.
Probably the leading example is primality testing. Even before it was known to be in P, I think many computer scientists still suspected that it was likely to be in P (based on an expectation that BPP = P), but a proof seemed well out of our reach.
Linear programming is another problem where it took a little while to find a polynomial-time algorithm. For a little while, we knew about the simplex algorithm, which was often efficient in practice but which is not polynomial-time in the worst case. Then Khachiyan proved that the ellipsoid algorithm runs in polynomial time, leading to new methods for solving linear programming problems.
There are some problems where a polynomial-time algorithm is not entirely trivial to find. For example, maximum matching or 2SAT are two examples where a new undergrad who looks at the problem might not immediately see a polynomial-time algorithm.
Context
StackExchange Computer Science Q#153663, answer score: 4
Revisions (0)
No revisions yet.