patternMinor
Pebble game lower bound?
Viewed 0 times
pebblelowergamebound
Problem
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?
Why is it not considered proof of constructive example for a function in $NP$ which requires superlinear runtime?
Solution
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.
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.
Context
StackExchange Computer Science Q#110042, answer score: 3
Revisions (0)
No revisions yet.