In the introduction and explanation P and NP complexity classes often given through Turing machine. One of the model of computation is the lambda-calculus. I understand, that all of models of computation are equivalent (and if we can introduce anything in terms Turing machine, we can introduce this in terms any model of computation), but I never seen explanation idea P and NP complexity classes through lambda-calculus. Can anybody explain notions P and NP complexity classes without Turing machine and only with lambda calculus as model of computation.
$\begingroup$
$\endgroup$
2
-
5$\begingroup$ Their computational power is equivalent only for functions over natural numbers, not higher types or other settings. $\endgroup$– KavehCommented Jun 6, 2014 at 9:17
-
$\begingroup$ Turing completeness is sometimes a more theoretical concept to show a connection but more applied "conversions" between TM complete systems are not always actually carried out in practice ie its sometimes more about existence proofs... $\endgroup$– vznCommented Jun 6, 2014 at 23:19
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
7
Turing-machines and $\lambda$-calculus are equivalent only w.r.t. the functions $\mathbb{N} \rightarrow \mathbb{N}$ they can define.
From the point of view of computational complexity they seem to behave differently. The main reason people use Turing machines and not $\lambda$-calculus to reason about complexity is that using $\lambda$-calculus naively leads to unrealistic complexity measures, because you can copy terms (of arbitrary size) freely in single $\beta$-reduction steps, e.g. $(\lambda x.xxx)M \rightarrow MMM.$ In other words, single reduction steps in $\lambda$-calculus are a lousy cost model. In contrast, single Turing-machine reduction steps work great (in the sense of being good predictors of real-world program run-time).
It is not known how fully to recover conventional Turing-machine based complexity theory in $\lambda$-calculus. In a recent (2014) breakthrough Accattoli and Dal Lago managed to show that large classes of time-complexity such as $P$, $NP$ and $EXP$ can be given a natural $\lambda$-calculus formulation. But smaller classes like $O(n^2)$ or $O(n \, log\, n)$ cannot be presented using the Accattoli / Dal Lago techniques.
How to recover conventional space complexity using $\lambda$-calculus is unknown.
answered Jun 6, 2014 at 9:08
-
5$\begingroup$ I feel the need to clarify here: there is no special "technique" Accattoli and Dal Lago use to "present" time classes. The presentation is the "naive" one: define $\lambda TIME(f(n))$ as the class of languages decidable by a $\lambda$-term in $f(n)$ $\beta$-reduction steps, under any standard reduction strategy (e.g. leftmost-outermost). Accattoli and Dal Lago showed, using techniques coming from linear logic, that there is a polynomial $p$ such that $\lambda TIME(f(n))=TIME(p(f(n))$. $\endgroup$ Commented Jun 9, 2014 at 9:26
-
$\begingroup$ @DamianoMazza Yes that's right, what I meant is that I don't think the techniques used to show this result can be used to show e.g. $\lambda TIME(n^2) = TIME(n^2)$. $\endgroup$ Commented Jun 9, 2014 at 10:36
-
3$\begingroup$ Ok, I see. Actually, my guess is that $\lambda TIME(n^2)\neq TIME(n^2)$: complexity classes such as $TIME(n^2)$ or $TIME(n\log n)$ are not robust, one cannot expect them to be stable under changes in the computational model (this is notoriously the case even if we stick to Turing machines, e.g. single-tape vs. multi-tape). $\endgroup$ Commented Jun 9, 2014 at 21:01
-
3$\begingroup$ @DamianoMazza I agree, likewise for the size of the chosen alphabet. But an algorithm running in $f(n)$ on an $n$-tape machine can be simulated in $5kf^2(n)$ on a 1-tape machine, a modest quadratic blowup. What's the blowup of the current translation of Accattoli and Dal Lago's? I don't remember if they explicitly state it. $\endgroup$ Commented Jun 9, 2014 at 21:41
-
1$\begingroup$ @Jake The cited paper discusses beta-normalization (see page two). Similar results were already known for other forms of reduction, like weak reduction (that is, call-by-value)—see Dal Lago & Martini, 2008 (discussed in that paper and in cstheory.stackexchange.com/a/397/989). $\endgroup$ Commented Jan 18, 2017 at 19:08
$\begingroup$
$\endgroup$
I paste part of an answer I wrote for another question:
Implicit Computational Complexity aims at characterizing complexity classes by means of dedicated languages. The first results such as Bellantoni-Cook's Theorem were stated in terms of $\mu$-recursive functions, but more recent results use the vocabulary and techniques of $\lambda$-calculus. See this Short introduction to Implicit Computational Complexity for more and pointers, or the proceedings of the DICE workshops.
There exist characterizations of (at least) $\mathsf{FP}$ by means of $\lambda$-calculus.
$\begingroup$
$\endgroup$
I don't know if this answers (part of) your question but there are indeed alternative characterizations of the complexity classes (esp. $\mathbb{P}$ and $\mathbb{NP}$) in terms of logics (1st order logic, 2nd order logic, etc..).
For example the work of R. Fagin (et al.) in this area is notable (and imo might provide insight related to the $\mathbb{P}$ vs $\mathbb{NP}$ issue and relations with descriptive and algorithmic complexity)
Some further characterizations of computational complexity classes in terms of algorithmic (Kolmogorov-Solomonov) complexity can be found (for example) here and here.
