<p>In Descriptive Complexity, consider the logical language consisting of two sorts: unary numbers
<span class="math-container">$x$</span> and binary string <span class="math-container">$Y$</span>, and <span class="math-container">$\{0,1,+,*, \leq, =\}$</span> on unary numbers (commutative discrete ordered semi-ring), <span class="math-container">$|Y| = x$</span> as the string length function, and <span class="math-container">$x \in Y$</span> as <span class="math-container">$x$</span>th bit of <span class="math-container">$Y$</span> being 1 (also written as <span class="math-container">$Bit(Y,x)$</span>.</p>
<p>Formulas with only bounded quantifiers over unary numbers captures uniform bounded-depth polynomial-size circuit families <span class="math-container">$\mathsf{AC^0}$</span>. That is any such function <span class="math-container">$f$</span>'s output bits can be represented by such a formula <span class="math-container">$\varphi(X,y)$</span> that gives <span class="math-container">$y$</span>th bit of <span class="math-container">$f(X)$</span>.</p>
<p><span class="math-container">$\mathsf{NP}$</span> can be defined by adding bounded existential quantifiers to above. Bounded here means the length of strings are bounded, e.g.
<span class="math-container">$$\varphi(X,y) := \exists Z (|Z| \leq |X|*|X|) \forall x \leq |X| ...$$</span></p>
<p><span class="math-container">$\mathsf{P}$</span> is a bit harder to define. There are two approaches:
The way way of to add a complete problem as a predicate to the language. E.g. you can add circuit value problem. It is closure under <span class="math-container">$\mathsf{AC^0}$</span> is <span class="math-container">$\mathsf{P}$</span>.</p>
<p>The harder way is to add some form of polynomial number of steps iteration to the language. Emil's answer is using bounded recursion with the bound being a polynomial of unary numbers. There are other ways to do it, e.g. using Least Fixed Point operators.</p>
<p>Another way is to use polynomial-size Boolean circuit + uniformity restriction (and for uniformity, you can use <span class="math-container">$\mathsf{AC^0}$</span> above).</p>
<p>Another way is to allow polynomially-many bounded unary quantifiers, since <span class="math-container">$\mathsf{P} = \mathsf{AltTime(poly,poly)}$</span> (though that is tricky because you need to enforce uniformity).</p>

CC BY-SA 4.0
2023-07-06T16:23:16.537Z
2023-07-06T16:23:16.537Z
Kaveh
<p><span class="math-container">$\def\cat{_\smile}$</span>Sure. By a classical result of Cobham, the set <strong>FP</strong> of polynomial-time functions can be described as the smallest set of functions <span class="math-container">$f\colon(\{0,1\}^*)^n\to\{0,1\}^*$</span> (<span class="math-container">$n\in\mathbb N$</span>) that contains the constant function <span class="math-container">$\epsilon$</span>, the functions <span class="math-container">$s_0(x)=x\cat0$</span>, <span class="math-container">$s_1(x)=x\cat1$</span>, <span class="math-container">$x\#y=\underbrace{x\cat\dots\cat x}_{|y|\text{ times}}$</span>, projections <span class="math-container">$\pi^n_i(x_0,\dots,x_{n-1})=x_i$</span>, and such that it is closed under composition and limited recursion on notation.</p>
<p>Here, an <span class="math-container">$(n+1)$</span>-ary function <span class="math-container">$f$</span> is defined by limited recursion on notation from an <span class="math-container">$n$</span>-ary function <span class="math-container">$g$</span>, <span class="math-container">$(n+2)$</span>-ary functions <span class="math-container">$h_0,h_1$</span>, and an <span class="math-container">$(n+1)$</span>-ary function <span class="math-container">$b$</span> if
<span class="math-container">$$\begin{align*}
f(\vec x,\epsilon)&amp;=g(\vec x),\\
f(\vec x,s_i(y))&amp;=h_i(\vec x,y,f(\vec x,y)),\\
|f(\vec x,y)|&amp;\le|b(\vec x,y)|
\end{align*}$$</span>
for all <span class="math-container">$\vec x\in(\{0,1\}^*)^n$</span>, <span class="math-container">$y\in\{0,1\}^*$</span>, and <span class="math-container">$i\in\{0,1\}$</span>.</p>
<p>(It is also straightforward to reformulate all this in terms of functions <span class="math-container">$\mathbb N^n\to\mathbb N$</span> instead of <span class="math-container">$(\{0,1\}^*)^n\to\{0,1\}^*$</span>, if desired.)</p>
<p>Once you have <strong>FP</strong>, you can define in the usual way <strong>P</strong> as the set of languages <span class="math-container">$L\subseteq\{0,1\}^*$</span> whose characteristic function is in <strong>FP</strong>, and <strong>NP</strong> as the set of languages <span class="math-container">$L\subseteq\{0,1\}^*$</span> such that
<span class="math-container">$$\forall x\in\{0,1\}^*\:\bigl[x\in L\iff\exists y\:\bigl(|y|\le p(|x|)\land R(x,y)\bigr)\bigr]$$</span>
for some polynomial <span class="math-container">$p$</span> and some polynomial-time relation <span class="math-container">$R$</span> (i.e., <span class="math-container">$R\subseteq(\{0,1\}^*)^2$</span> whose characteristic function is in <strong>FP</strong>).</p>
<hr />
<p>NB: The choice of basic functions and operations in Cobham’s characterization is perfectly analogous to the definition of primitive recursive functions. The latter are based on the characterization of natural numbers (considered as written in unary) as the <a href="https://en.wikipedia.org/wiki/Initial_algebra" rel="noreferrer">initial algebra</a> with a constant <span class="math-container">$0$</span> and the successor function <span class="math-container">$s(x)$</span>.</p>
<p>Here, <span class="math-container">$\{0,1\}^*$</span> is treated as the initial algebra with a constant <span class="math-container">$\epsilon$</span> and two successor functions <span class="math-container">$s_0(x)$</span> and <span class="math-container">$s_1(x)$</span>. To that end, we have <span class="math-container">$\epsilon$</span>, <span class="math-container">$s_0$</span>, and <span class="math-container">$s_1$</span> as basic functions, and we have the corresponding recursion schema (recursion on notation). Moreover, we have the usual universal algebra facilities (projections, composition) to construct functions by terms.</p>
<p>Except that if we did just that, we would end up with all primitive recursive functions again. In order to make all the functions polynomial-time computable, we restrict the recursion schema with the limits <span class="math-container">$b$</span>, ensuring we cannot use it to build functions growing faster than already constructed functions. But now we have the opposite problem: we need to make sure some functions of polynomial growth (in terms of length) <em>can</em> be constructed. To this end, we include as the last basic function the <span class="math-container">$\#$</span> function, whose finite iterates bound every polynomially bounded function.</p>

CC BY-SA 4.0
2023-07-03T21:53:42.840Z
Beautiful, thanks Emil!!
Dominic van der Zypen
CC BY-SA 4.0
2023-07-04T05:55:19.657Z
Oh, a few clarifying questions on your notation. 1) By the "constant function" $\epsilon:(\{0,1\}^*)^n \to \{0,1\}^*$ you mean all constant functions (sending elements of $(\{0,1\}^*)^n$ to a *fixed* element of $\{0,1\}^*$) ? 2) Can you briefly write down the meaning of $x _{\smile} 0,1\ldots$? Oh - I guess they are concatenations? Many thanks in advance!
Dominic van der Zypen
CC BY-SA 4.0
2023-07-04T06:42:15.223Z
As usual, $\epsilon$ denotes the empty string. As a constant function, it denotes the function $\{0,1\}^*\to\{0,1\}^*$ that maps every string to $\epsilon$. Or even better, if you allow $n$ to be $0$, you can identify a constant $c\in\{0,1\}^*$ with a function $(\{0,1\}^*)^0\to\{0,1\}^*$ whose value on the single argument is $c$; so then you can take $\epsilon$ to be such a function. And yes, ${}_\smile$ is concatenation.
Emil Jeřábek
CC BY-SA 4.0
2023-07-03T20:55:03.797Z
2023-07-04T09:47:23.067Z
2023-07-04T09:47:23.067Z
Emil Jeřábek
<p>Computability in terms of Turing machines is equivalent to computability described by computable functions (based on primitive recursive functions, introducing the <span class="math-container">$\mu$</span>-operator and so on). Is there a natural formulation of P vs NP in terms of computable functions?</p>

CC BY-SA 4.0
2023-07-03T20:44:22.823Z
Just a comment since I am too far from the topic to be totally relevant: this is akin to a domain known as implicit complexity where the model of computation is restricted in a way that makes it capture some complexity class. For example, Bellantoni and Cook proved that some restriction of the recursion scheme of recursive function captures P (S. Bellantoni and S. Cook. *A new recursion-theoretic characterization of the poly-time
functions.* Computational Complexity, 1992).
holf
CC BY-SA 4.0
2023-07-03T20:45:15.643Z
To be clear, the notion of "computable function" *requires* a machine model of which recursive functions with unbounded recursion is an example (as is the $\lambda$-calculus). I think you're asking for a machine model that is "qualitatively different" than Turing Machines?
cody
CC BY-SA 4.0
2023-07-04T12:59:53.363Z
@dominic I really much appreciate you asking this question! I've been curious as well.
mathworker21
CC BY-SA 4.0
2023-07-04T16:36:38.870Z
Thank you @mathworker21!
Dominic van der Zypen
CC BY-SA 4.0
2023-07-05T05:05:45.040Z
It wouldn't make for an on-topic answer, but in addition to implicit complexity, there's also [descriptive complexity theory](https://en.wikipedia.org/wiki/Descriptive_complexity_theory).
Corbin
CC BY-SA 4.0
2023-07-05T13:47:56.573Z
Thanks @corbin!
Dominic van der Zypen
<p-vs-np>
Formulating P vs NP without Turing machines
Dominic van der Zypen
# Formulating P vs NP without Turing machines

(Asked by: username_0 on 2023-07-03)

Computability in terms of Turing machines is equivalent to computability described by computable functions (based on primitive recursive functions, introducing the $\mu$-operator and so on). Is there a natural formulation of P vs NP in terms of computable functions?

**Tags:** p-vs-np
> **Comments:**
> **username_1**: Just a comment since I am too far from the topic to be totally relevant: this is akin to a domain known as implicit complexity where the model of computation is restricted in a way that makes it capture some complexity class. For example, Bellantoni and Cook proved that some restriction of the recursion scheme of recursive function captures P (S. Bellantoni and S. Cook. *A new recursion-theoretic characterization of the poly-time functions.* Computational Complexity, 1992).  
> **username_2**: To be clear, the notion of "computable function" *requires* a machine model of which recursive functions with unbounded recursion is an example (as is the $\lambda$-calculus). I think you're asking for a machine model that is "qualitatively different" than Turing Machines?  
> **username_3**: @dominic I really much appreciate you asking this question! I've been curious as well.  
> **username_0**: Thank you @mathworker21!  
> **username_4**: It wouldn't make for an on-topic answer, but in addition to implicit complexity, there's also [descriptive complexity theory](https://en.wikipedia.org/wiki/Descriptive_complexity_theory).  
> **username_0**: Thanks @corbin!  

---

## 2 answers

### Answer by username_6 on 2023-07-03. Score: 13 | Accepted answer

$\def\cat{\_\smile}$Sure. By a classical result of Cobham, the set **FP** of polynomial-time functions can be described as the smallest set of functions $f\colon(\{0,1\}^\*)^n\to\{0,1\}^\*$ ($n\in\mathbb N$) that contains the constant function $\epsilon$, the functions $s\_0(x)=x\cat0$, $s\_1(x)=x\cat1$, $x\#y=\underbrace{x\cat\dots\cat x}\_{|y|\text{ times}}$, projections $\pi^n\_i(x\_0,\dots,x\_{n-1})=x\_i$, and such that it is closed under composition and limited recursion on notation.

Here, an $(n+1)$-ary function $f$ is defined by limited recursion on notation from an $n$-ary function $g$, $(n+2)$-ary functions $h\_0,h\_1$, and an $(n+1)$-ary function $b$ if
$$\begin{align\*}
f(\vec x,\epsilon)&=g(\vec x),\\
f(\vec x,s\_i(y))&=h\_i(\vec x,y,f(\vec x,y)),\\
|f(\vec x,y)|&\le|b(\vec x,y)|
\end{align\*}$$
for all $\vec x\in(\{0,1\}^\*)^n$, $y\in\{0,1\}^\*$, and $i\in\{0,1\}$.

(It is also straightforward to reformulate all this in terms of functions $\mathbb N^n\to\mathbb N$ instead of $(\{0,1\}^\*)^n\to\{0,1\}^\*$, if desired.)

Once you have **FP**, you can define in the usual way **P** as the set of languages $L\subseteq\{0,1\}^\*$ whose characteristic function is in **FP**, and **NP** as the set of languages $L\subseteq\{0,1\}^\*$ such that
$$\forall x\in\{0,1\}^\*\:\bigl[x\in L\iff\exists y\:\bigl(|y|\le p(|x|)\land R(x,y)\bigr)\bigr]$$
for some polynomial $p$ and some polynomial-time relation $R$ (i.e., $R\subseteq(\{0,1\}^\*)^2$ whose characteristic function is in **FP**).

---

NB: The choice of basic functions and operations in Cobham’s characterization is perfectly analogous to the definition of primitive recursive functions. The latter are based on the characterization of natural numbers (considered as written in unary) as the [initial algebra](https://en.wikipedia.org/wiki/Initial_algebra) with a constant $0$ and the successor function $s(x)$.

Here, $\{0,1\}^\*$ is treated as the initial algebra with a constant $\epsilon$ and two successor functions $s\_0(x)$ and $s\_1(x)$. To that end, we have $\epsilon$, $s\_0$, and $s\_1$ as basic functions, and we have the corresponding recursion schema (recursion on notation). Moreover, we have the usual universal algebra facilities (projections, composition) to construct functions by terms.

Except that if we did just that, we would end up with all primitive recursive functions again. In order to make all the functions polynomial-time computable, we restrict the recursion schema with the limits $b$, ensuring we cannot use it to build functions growing faster than already constructed functions. But now we have the opposite problem: we need to make sure some functions of polynomial growth (in terms of length) *can* be constructed. To this end, we include as the last basic function the $\#$ function, whose finite iterates bound every polynomially bounded function.

> **Comments:**
> **username_0**: Beautiful, thanks Emil!!  
> **username_0**: Oh, a few clarifying questions on your notation. 1) By the "constant function" $\epsilon:(\{0,1\}^*)^n \to \{0,1\}^*$ you mean all constant functions (sending elements of $(\{0,1\}^*)^n$ to a *fixed* element of $\{0,1\}^*$) ? 2) Can you briefly write down the meaning of $x _{\smile} 0,1\ldots$? Oh - I guess they are concatenations? Many thanks in advance!  
> **username_6**: As usual, $\epsilon$ denotes the empty string. As a constant function, it denotes the function $\{0,1\}^*\to\{0,1\}^*$ that maps every string to $\epsilon$. Or even better, if you allow $n$ to be $0$, you can identify a constant $c\in\{0,1\}^*$ with a function $(\{0,1\}^*)^0\to\{0,1\}^*$ whose value on the single argument is $c$; so then you can take $\epsilon$ to be such a function. And yes, ${}_\smile$ is concatenation.  

---

### Answer by username_5 on 2023-07-06. Score: 2

In Descriptive Complexity, consider the logical language consisting of two sorts: unary numbers
$x$ and binary string $Y$, and $\{0,1,+,\*, \leq, =\}$ on unary numbers (commutative discrete ordered semi-ring), $|Y| = x$ as the string length function, and $x \in Y$ as $x$th bit of $Y$ being 1 (also written as $Bit(Y,x)$.

Formulas with only bounded quantifiers over unary numbers captures uniform bounded-depth polynomial-size circuit families $\mathsf{AC^0}$. That is any such function $f$'s output bits can be represented by such a formula $\varphi(X,y)$ that gives $y$th bit of $f(X)$.

$\mathsf{NP}$ can be defined by adding bounded existential quantifiers to above. Bounded here means the length of strings are bounded, e.g.
$$\varphi(X,y) := \exists Z (|Z| \leq |X|\*|X|) \forall x \leq |X| ...$$

$\mathsf{P}$ is a bit harder to define. There are two approaches:
The way way of to add a complete problem as a predicate to the language. E.g. you can add circuit value problem. It is closure under $\mathsf{AC^0}$ is $\mathsf{P}$.

The harder way is to add some form of polynomial number of steps iteration to the language. Emil's answer is using bounded recursion with the bound being a polynomial of unary numbers. There are other ways to do it, e.g. using Least Fixed Point operators.

Another way is to use polynomial-size Boolean circuit + uniformity restriction (and for uniformity, you can use $\mathsf{AC^0}$ above).

Another way is to allow polynomially-many bounded unary quantifiers, since $\mathsf{P} = \mathsf{AltTime(poly,poly)}$ (though that is tricky because you need to enforce uniformity).


---

