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:

  • 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


1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.