# 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 at 11:56
• @YuvalFilmus Then what is the problem about looking for problems in $NP$ needing superlinear lower bound? Is it about circuits? – T.... May 31 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 at 12:49
• One approach is via circuits. For general circuits, the best lower bound for explicit functions is linear. – Yuval Filmus May 31 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. – T.... May 31 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.