<p>Sipser proved that no infinite parity can be computed by an (infinite) circuit of any constant depth, which you can view as a warm-up to the result that PARITY is not in $AC^0$. </p>

<p>There are also some results and attempts at proofs of lower bounds in proof complexity using nonstandard models (some results of Ajtai and Krajicek. See esp. Krajiceks' "Forcing with Random Variables and Proof Complexity," available from Cambridge Press, but also a <a href="http://www.karlin.mff.cuni.cz/~krajicek/fdraft.html">draft available online</a>) . The basic idea is to build a nonstandard model of arithmetic in which a statement is <em>false</em> in the model (rather than "true, but without short proofs"), and then, from the properties of the model, infer that a corresponding sequence of finite statements does not have polynomial-size proofs in some proof system. </p>

<p>I'm not sure, but my impression is that often these results sort of "hide the asymptotics under the hood" so that it's not so much a reduction from threshold to finiteness as it is a new mathematical language in which "false" in the new language corresponds to "without short proofs" in the old language. That's not to say that the new language doesn't provide a useful new viewpoint, but I'm not quite sure if it's what you're looking for.</p>

CC BY-SA 3.0
2013-07-30T19:04:42.527Z
2013-07-30T19:04:42.527Z
Joshua Grochow
<p>The fields of descriptive complexity, and implicit complexity could be viewed as taking this kind of approach. They both turn a resource constraint (like $P$ or $NP$) into expressibility of the problem in a logical formalism (for descriptive complexity) or in a specific programming language (for implicit complexity).</p>

<p>So it is not per se related to infinite computation, but rather to expressibility of the problem in a given model. However it is close in the sense that it turns a quantitative problem into a qualitative one.</p>

CC BY-SA 3.0
2013-05-29T13:06:05.080Z
2013-05-29T13:06:05.080Z
Denis
<p>It is usually simpler to reason about calculus where the limitation is finiteness of computation rather than a threshold like "computable in polynomial amount of time".</p>

<p>In formal languages theory for example, rather to use the $\exists n. x^{n+1} = x^n$ to characterize aperiodic monoïd, it is easier to use profinite words so that $x^{\omega+1} = x^{\omega}$.</p>

<p>In complexity theory, the only technic I know which is linked to that is the <em>padding trick</em> for example linking the problem of P vs NP to EXPTIME vs NEXPTIME. But the natural infinite equivalent of complexity questions would be computability ones'.</p>

<blockquote>
  <p>Are there some results that link complexity to computability questions using some encoding such that the resource threshold of complexity theory becomes a finiteness question of computation in computability theory ?</p>
</blockquote>

CC BY-SA 3.0
2013-07-30T17:58:27.933Z
Your example of profinite words is reminiscent of nonstandard arithmetic and analysis. From this viewpoint, one can view polynomial versus super-polynomial as the following finiteness question (I realize this is sort of a hack, but I think it's similar to the profinite word trick): Let $T(n)$ be the max runtime of Turing machine $M$ on inputs of length $n$. Then $M$ runs in polynomial time iff $\limsup_{n \to \infty} \log T(n) / n$ is finite. Probably this can be turned into a strange "profinite" model of computation in which the preceding expression really is the "runtime" in that model.
Joshua Grochow
<cc.complexity-theory><computability>
Reducing threshold questions to finiteness questions
Ludovic Patey
# Reducing threshold questions to finiteness questions

(Asked by: username_0 on 2011-12-15)

It is usually simpler to reason about calculus where the limitation is finiteness of computation rather than a threshold like "computable in polynomial amount of time".

In formal languages theory for example, rather to use the $\exists n. x^{n+1} = x^n$ to characterize aperiodic monoïd, it is easier to use profinite words so that $x^{\omega+1} = x^{\omega}$.

In complexity theory, the only technic I know which is linked to that is the *padding trick* for example linking the problem of P vs NP to EXPTIME vs NEXPTIME. But the natural infinite equivalent of complexity questions would be computability ones'.

> Are there some results that link complexity to computability questions using some encoding such that the resource threshold of complexity theory becomes a finiteness question of computation in computability theory ?

**Tags:** cc.complexity-theory, computability

> **Comments:**
> **username_1**: Your example of profinite words is reminiscent of nonstandard arithmetic and analysis. From this viewpoint, one can view polynomial versus super-polynomial as the following finiteness question (I realize this is sort of a hack, but I think it's similar to the profinite word trick): Let $T(n)$ be the max runtime of Turing machine $M$ on inputs of length $n$. Then $M$ runs in polynomial time iff $\limsup_{n \to \infty} \log T(n) / n$ is finite. Probably this can be turned into a strange "profinite" model of computation in which the preceding expression really is the "runtime" in that model.  

---

## 2 answers

### Answer by username_1 on 2013-07-30. Score: 5

Sipser proved that no infinite parity can be computed by an (infinite) circuit of any constant depth, which you can view as a warm-up to the result that PARITY is not in $AC^0$.

There are also some results and attempts at proofs of lower bounds in proof complexity using nonstandard models (some results of Ajtai and Krajicek. See esp. Krajiceks' "Forcing with Random Variables and Proof Complexity," available from Cambridge Press, but also a [draft available online](http://www.karlin.mff.cuni.cz/~krajicek/fdraft.html)) . The basic idea is to build a nonstandard model of arithmetic in which a statement is *false* in the model (rather than "true, but without short proofs"), and then, from the properties of the model, infer that a corresponding sequence of finite statements does not have polynomial-size proofs in some proof system.

I'm not sure, but my impression is that often these results sort of "hide the asymptotics under the hood" so that it's not so much a reduction from threshold to finiteness as it is a new mathematical language in which "false" in the new language corresponds to "without short proofs" in the old language. That's not to say that the new language doesn't provide a useful new viewpoint, but I'm not quite sure if it's what you're looking for.


---

### Answer by username_2 on 2013-05-29. Score: 4

The fields of descriptive complexity, and implicit complexity could be viewed as taking this kind of approach. They both turn a resource constraint (like $P$ or $NP$) into expressibility of the problem in a logical formalism (for descriptive complexity) or in a specific programming language (for implicit complexity).

So it is not per se related to infinite computation, but rather to expressibility of the problem in a given model. However it is close in the sense that it turns a quantitative problem into a qualitative one.


---

