3
$\begingroup$

I'm currently reading Introduction to the Theory of Computation by Michael Sipser and in his section on time complexity, he tries to justify why theoretical computer scientists divide problems into P and NP.

First he says:

$P$ roughly corresponds to the class of problems that are realistically solvable on a computer.

He then continues a little further down the page:

Of course, a running time of $n^{100}$ is unlikely to be of any practical use. Nevertheless, calling polynomial time the threshold of practical solvability has proven to be useful. Once a polynomial time algorithm has been found for a problem that formerly appeared to require exponential time, some key insight into it has been gained and further reductions in its complexity usually follow, often to the point of actual practical utility.

So my question is the following: What are examples of problems that were proven to be in P but were intractable, but after some theoretical advances became tractable?

I'm also welcome to hearing about problems that were proven to be in P whose runtime was significantly advanced by some algorithmic improvements but perhaps was not advanced enough to be tractable.

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ Duplicate? This one is also related. Bottom line: the first statement by Sipser is probably plain wrong. $\endgroup$
    – Raphael
    Commented Nov 1, 2015 at 18:53
  • 2
    $\begingroup$ I disagree with Sisper. It's a false belief. Indeed, the time hierarchy theorem ensures that there are problems in P that can't be solved in say $O(n^{100})$. $\endgroup$
    – Yuval Filmus
    Commented Nov 1, 2015 at 19:43
  • 1
    $\begingroup$ I'm not sure it's worth arguing about what's obviously intended to be an informal, introductory statement that includes the word "roughly". $\endgroup$
    – David Richerby
    Commented Nov 1, 2015 at 21:18
  • $\begingroup$ I'm not really arguing with Sipser. I'm just looking for examples of problems of the type he describes in the second excerpt. $\endgroup$
    – user35734
    Commented Nov 1, 2015 at 22:30
  • 1
    $\begingroup$ Relevant? $\endgroup$
    – adrianN
    Commented Nov 2, 2015 at 15:30

1 Answer 1

Reset to default
2
$\begingroup$

One example in which the running time became significantly better but still not necessarily practical is submodular function minimization, which went down from $O(n^7)$ (Grötschel, Lovász and Schrijver, 1981) to $\tilde{O}(n^4)$ (Lee, Sidford and Wong, 2015). The latter paper (and the ones preceding it) has many such results.

Improve this answer
$\endgroup$

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