11
$\begingroup$

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?

$\endgroup$
6
  • 2
    $\begingroup$ 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). $\endgroup$
    – holf
    Jul 3, 2023 at 20:44
  • 2
    $\begingroup$ 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? $\endgroup$
    – cody
    Jul 3, 2023 at 20:45
  • 3
    $\begingroup$ @dominic I really much appreciate you asking this question! I've been curious as well. $\endgroup$ Jul 4, 2023 at 12:59
  • $\begingroup$ Thank you @mathworker21! $\endgroup$ Jul 4, 2023 at 16:36
  • 3
    $\begingroup$ It wouldn't make for an on-topic answer, but in addition to implicit complexity, there's also descriptive complexity theory. $\endgroup$
    – Corbin
    Jul 5, 2023 at 5:05

2 Answers 2

13
$\begingroup$

$\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 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.

$\endgroup$
3
  • 1
    $\begingroup$ Beautiful, thanks Emil!! $\endgroup$ Jul 3, 2023 at 21:53
  • 2
    $\begingroup$ 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! $\endgroup$ Jul 4, 2023 at 5:55
  • 2
    $\begingroup$ 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. $\endgroup$ Jul 4, 2023 at 6:42
2
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.