<p>Something like this is used in the definition of creative sets by Joseph and Young (1985). See <a href="https://en.wikipedia.org/wiki/Polynomial_creativity" rel="nofollow noreferrer">the Wikipedia article on polynomial creativity</a>. But their use is to concoct NP-hard sets with unusual properties (potential counterexamples to the Berman–Hartmanis conjecture rather than to say anything nontrivial about the complexity of any natural algorithmic problem.</p>

CC BY-SA 4.0
2019-11-22T23:55:51.407Z
2019-11-22T23:55:51.407Z
David Eppstein
<p>Has there ever been a proof technique to show that a language isn't in <span class="math-container">$\mathrm{P}$</span>, by showing inductively there isn't any <span class="math-container">$k$</span> for which the language is in <span class="math-container">$\mathrm{TIME}(n^k)$</span>?</p>

<p>e.g.: <span class="math-container">$L\notin \mathrm{TIME}(n^0)$</span>,</p>

<p><span class="math-container">$L\notin \mathrm{TIME}(n^k)\rightarrow L\notin \mathrm{TIME}(n^{k+1})$</span>,</p>

<p><span class="math-container">$\therefore L\notin \mathrm{P}$</span>.</p>

<p>Is something of the sort feasible? Has it been used? </p>

<time-complexity><polynomial-time>
Induction on all polynomial runtimes?
bitconfused
# Induction on all polynomial runtimes?

(Asked by: username_0 on 2019-11-22)

Has there ever been a proof technique to show that a language isn't in $\mathrm{P}$, by showing inductively there isn't any $k$ for which the language is in $\mathrm{TIME}(n^k)$?

e.g.: $L\notin \mathrm{TIME}(n^0)$,

$L\notin \mathrm{TIME}(n^k)\rightarrow L\notin \mathrm{TIME}(n^{k+1})$,

$\therefore L\notin \mathrm{P}$.

Is something of the sort feasible? Has it been used?

**Tags:** time-complexity, polynomial-time


---

## 1 answers

### Answer by username_1 on 2019-11-22. Score: 3

Something like this is used in the definition of creative sets by Joseph and Young (1985). See [the Wikipedia article on polynomial creativity](https://en.wikipedia.org/wiki/Polynomial_creativity). But their use is to concoct NP-hard sets with unusual properties (potential counterexamples to the Berman–Hartmanis conjecture rather than to say anything nontrivial about the complexity of any natural algorithmic problem.


---

