# Pebble game lower bound?

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?

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

## 1 Answer

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.

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