Witness length independent $\exists$-Operator

Question

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.

Answer 1

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

Answer 2

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