This paper says pebble games have super linear lower bound for every fixed $k$ https://dl.acm.org/citation.cfm?doid=62.322433.

Why is it not considered proof of constructive example for a function in $NP$ which requires superlinear runtime?

  • $\begingroup$ The time hierarchy theorem already gives explicit examples of problems in P which require superlinear runtime. $\endgroup$ – Yuval Filmus May 31 '19 at 11:56
  • $\begingroup$ @YuvalFilmus Then what is the problem about looking for problems in $NP$ needing superlinear lower bound? Is it about circuits? $\endgroup$ – 1.. May 31 '19 at 12:14
  • $\begingroup$ We're looking for a problem in NP which needs superpolynomial time. This is the P vs NP question. $\endgroup$ – Yuval Filmus May 31 '19 at 12:49
  • $\begingroup$ One approach is via circuits. For general circuits, the best lower bound for explicit functions is linear. $\endgroup$ – Yuval Filmus May 31 '19 at 12:50
  • $\begingroup$ Yes I know that. In comm complexity multiparty nof lower bound implies some superlinear circuit lower bound and also I think in pseudoranfom generator. $\endgroup$ – 1.. May 31 '19 at 12:51

The time hierarchy theorem gives, for every $k$, a function in P with a runtime lower bound of $\Omega(n^k)$. Unfortunately, this is not enough to separate P from NP: to do this, we need a function in NP with a superpolynomial runtime lower bound.

One popular approach for tackling the P vs NP question is via circuits. The best lower bounds for explicit functions are only linear. Perhaps this is the context in which you heard of superlinear lower bounds as a seeming barrier.

  • $\begingroup$ precisely what I was looking for. $\endgroup$ – 1.. May 31 '19 at 14:30
  • $\begingroup$ @Brout if this is precisely the answer maybe you could consider marking it as one? $\endgroup$ – Evil Jun 1 '19 at 5:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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