Short version:

Is there an operator $\exists$ (on complexity classes) s.t. $\exists P = NP$ and $\exists REC=RE$, i.e. you can use the same operator on multiple interesting classes without explicitly stating a class of functions that limits the length of the witnesses? The construction should not rely on the existence of a definition of the class using any specific computation model (like Turing machines), i.e. it should be defined for any class of languages.

Long Version:

For any complexity class $\mathcal{C}$, any language $L$ and any class of functions $F\subseteq\{f|f:\mathbb{N}\rightarrow\mathbb{N}\}$ define

$$\exists^{f,\#} L =\{x \in (\Sigma\setminus\{\#\})^*|\exists w\in(\Sigma\setminus\{\#\})^*: x\#w \in L, |w| \leq f(|x|) \}$$ $$\exists^F \mathcal{C} =\{L|\exists\#\exists f\in F\exists L'\in\mathcal{C}:L=\exists^{f,\#} L'\} \qquad .$$

Note: If $F=\mathbb{N}^{\mathbb{N}} = \{f|f:\mathbb{N}\rightarrow\mathbb{N}\}$ the length of the witness $w$ becomes unrestricted (set $f(n)$ to be the maximum length of a witness for all inputs of size $n$).

It is well known that $NP=\exists^pP$, where $p$ is the set of all polynomials (see WP:Polynomial hierarchy) and $\exists^{\mathbb{N}^{\mathbb{N}}}REC=RE$ (see WP:Arithmetical hierarchy).

Now I'd like to know, if one could get rid of the class of functions $F$ or define $F$ depending on the class $\mathcal{C}$ without using a certain way to define the class (Not: If $\mathcal{C}$ is the class of languages accepted by a TM in $\mathrm{DTIME}(\dots)$, then $F:=\dots$)

Things I've tried so far:

  1. $\exists\mathcal{C} = \exists^F\mathcal{C} \text{ where } \exists^{o(F)}\mathcal{C} \subseteq \mathcal{C} \text{ and } \exists^F\mathcal{C}\nsubseteq \mathcal{C}$
  2. $\exists\mathcal{C} = \exists^{F'}\mathcal{C} \text{ where } F'=\{2^f|f\in F\} \text{ and } F \text{ maximal s.t. } \exists^{F}\mathcal{C} \subseteq \mathcal{C}$
  3. (added:) $\exists\mathcal{C} = \exists^F\mathcal{C} \text{ where } F=\{f\,|\,\forall L\forall\#\notin\Sigma(L):\, \{\#^{f(|w|)}w|w\in L\} \in \mathcal{C} \Leftrightarrow L \in \mathcal{C}\}$, i.e. those functions s.t. $\mathcal{C}$ is "invariant" under padding ($\Sigma(L)=\{a|\exists i\exists w_1,\dots,w_k \in L:\, w_i = a \}$).

1 and 2 don't work for P, I'm not sure about 3.

  • $\begingroup$ Does the witness for the P-instance need to be polynomial size? After all, in polynomially-bounded time one can only retrieve (for whatever definition of 'retrieve' you care to apply to the problem at hand) polynomially many bits of it, so it would seem that its actual size is moot... $\endgroup$ Mar 6, 2013 at 17:13
  • 1
    $\begingroup$ Yes it needs to be polynomial size, since the input size of the verifier is $|x|+|w|+1$. So superpolynomial size in $|x|$ means superpolynomial runtime (see en.wikipedia.org/wiki/Padding_argument). $\endgroup$
    – frafl
    Mar 6, 2013 at 17:20
  • $\begingroup$ @StevenStadnicki: Thank's, your question was a hint towards padding (see 3.). $\endgroup$
    – frafl
    Mar 7, 2013 at 14:47
  • $\begingroup$ Minor nitpickery: while I understand what you're getting at with it, the $\forall \#\notin\Sigma(L)$ notation is likely to be fairly tricky to formalize correctly. With that said, I'm pretty sure 3 represents NP correctly. $\endgroup$ Mar 8, 2013 at 0:20
  • $\begingroup$ @StevenStadnicki: What is trickery about it? $\forall \#\notin\Sigma(L)\dots$ is $\forall\#(\#\notin\Sigma(L)\Rightarrow\dots)$ and it's no problem to quantify over all sets in ZFC. $\endgroup$
    – frafl
    Mar 8, 2013 at 10:33

2 Answers 2


You don't need a witness at all. You can allow the Turing machine to make a non-deterministic "guess" at any time. A string is accepted iff there is a sequence of guesses that make the Turing machine accept it, otherwise it is rejected.

Edit: If you want a definition which does not rely on the machine model, then it would be a bit awkward. Here is one example, which includes a cheat - using the associated function class. Given a (time) complexity $C$ and its associated function class $FC$, the allowed witness lengths are parametrized by $f \in FC$: the lengths are given by $n \mapsto |f(0^n)|$.

  • $\begingroup$ Sorry, I don't understand this. I explicitly asked for a construction that does not rely on a specific computation model (like TM). Perhaps I should add a phrase like that to the short version, too. $\endgroup$
    – frafl
    Mar 6, 2013 at 16:34
  • $\begingroup$ This cheat doesn't work in the general case, what's $FC$ for $C=\{ \{ 0,1,\#\}^*\}$? Also this gives little insight. $\endgroup$
    – frafl
    Mar 6, 2013 at 19:53
  • 1
    $\begingroup$ Well, why do you think that such a general construction should exist? $\endgroup$ Mar 6, 2013 at 20:26
  • $\begingroup$ What do you mean by "should"? 1."desirable": It's always nice to unify similar concepts. Plus I'd like to see what happens if one tries to construct something that e.g. captures the "polynomiality" of P regardless of whether you use Turing machines or descriptive complexity. 2."I assume there is such a construction": I don't, but a hint why their can't be one is as interesting as a positive answer. $\endgroup$
    – frafl
    Mar 6, 2013 at 21:04
  • 1
    $\begingroup$ Seems you might have found a way to implement my "cheat" without cheating... $\endgroup$ Mar 7, 2013 at 16:21

As already suggested by Yuval Filmus and Steven Stadnicki, (3) works for $\mathrm{P}$. I'll elaborate on this:

Let $\Sigma(L)=\{a\mid\exists i\exists w_1,\dots,w_k \in L:\, w_i = a \}$ the set of symbols used by any word in $L$. Now take a symbol $\#\notin\Sigma(L)$ and a function $f:\mathbb{N}\rightarrow\mathbb{N}$, we define: $$\mathrm{padded}(L,f,\#) = \{\#^{f(|w|)}w \mid w\in L\}\qquad.$$

We observe, that if $f$ can be computed in $\mathrm{FL}$:

$$\mathrm{padded}(L,f,\#) \equiv_1^{\log} L\quad,$$

since we only need to remove the padding (constant space) or count the symbols, calculate $f(|w|)$ and pad (logarithmic space). As a result polynomials are allowed (s.b.) for all classes s.t. a polynomial longer input does not offer extra resources (e.g. $\log (|w|^k)=k\log |w|$).

For any complexity class $\mathcal{C}$ define $$\mathrm{FPR}(\mathcal{C})=\{f\mid\forall L\forall\#\notin\Sigma(L):\, \mathrm{padded}(L,f,\#) \in \mathcal{C} \Leftrightarrow L \in \mathcal{C}\}$$ the class of functions under which $\mathcal{C}$ is resistant to padding.

Also, we define an equivalence on function classes $F,F'$ where each one is an upper bound for the other:

$$F \lessapprox F' :\Leftrightarrow \forall f \in F\exists f'\in F'\forall x\in\mathbb{N}:f(x)\leq f'(x)$$ $$F \approxeq F' :\Leftrightarrow F \lessapprox F' \wedge F' \lessapprox F$$

Then, by using the space hierarchy theorem, the time hierarchy theorem and a variant for alternating TMs (see cstheory.se/4895) to exclude super polynomial (super linear) padding:

$$\mathrm{FPR}(\mathrm{L}) \approxeq \mathrm{FPR}(\mathrm{P}) \approxeq \mathrm{FPR}(\mathrm{NP})\approxeq \mathrm{FPR}(\Sigma_i^p)\\ \approxeq\mathrm{FPR}(\mathrm{PSPACE}) \approxeq \mathrm{FPR}(\mathrm{EXP}) \approxeq p$$ $$\mathrm{FPR}(\mathrm{LINSPACE}) \approxeq \mathrm{FPR}(\mathrm{E}) \approxeq l$$

where $p$ / $l$ ist the set of all polynomials/linear functions respectively.

So if we define $$\exists_{\mathrm{FPR}}\mathcal{C} := \exists^{\mathrm{FPR}(\mathcal{C})}\mathcal{C}\cup \mathcal{C}\qquad,$$ we get an operator that works like $\exists^p$ for $\mathrm{P}$ and the entire $\mathrm{PH}$ (including $\exists_{\mathrm{FPR}}\Sigma^p_i=\Sigma^p_i$).

To apply the operator to $\mathrm{REC}$, we observe that for any $L \in \mathrm{REC}$ a TM accepts $w\in L$ halting after a computable number of steps. Since we can use the series of configurations as a witness, $\exists_{\mathrm{FPR}}\mathrm{REC} = RE$, even though $\mathrm{FPR}(\mathrm{REC}) \not\approxeq \mathbb{N}^\mathbb{N}$ (e.g. WP:Buzy Beaver).


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.