1
$\begingroup$

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.

$\endgroup$
  • $\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$ – Steven Stadnicki Mar 6 '13 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 '13 at 17:20
  • $\begingroup$ @StevenStadnicki: Thank's, your question was a hint towards padding (see 3.). $\endgroup$ – frafl Mar 7 '13 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$ – Steven Stadnicki Mar 8 '13 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 '13 at 10:33
2
$\begingroup$

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

$\endgroup$
  • $\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 '13 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 '13 at 19:53
  • 1
    $\begingroup$ Well, why do you think that such a general construction should exist? $\endgroup$ – Yuval Filmus Mar 6 '13 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 '13 at 21:04
  • 1
    $\begingroup$ Seems you might have found a way to implement my "cheat" without cheating... $\endgroup$ – Yuval Filmus Mar 7 '13 at 16:21
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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