What complexity class is this?

Question

Disclaimer 1: I am a beginner in this domain and I am self-learning these concepts. Please take this in consideration when reading my question.

Disclaimer 2: All corrections to this question are highly encouraged. All self-learning PDF books etc. that helped you better understand these particular concepts are highly desired.

Hello,

In this question, I assume I have some formal definition of the Turing machine such that:

1. any Turing machine (say $M$) can receive exactly:
   • one input $i$, where $i \in \{0,1\}^*$ ;
   • one witness $w$, where $w \in \{0,1\}^*$ and $\exists \, a \in \mathbb{N} : |w| \le |i|^a$. I call such a witness "a witness of the input $i$". By $|x|$ I mean the length of the string $x$.
2. $M$ is able to compute with $i$ and $w$ and:
   • loop, if the computation lasts forever. I write $M(i, w) = {\nearrow}$ to denote this
   • halt, if the computation ends at some point. Here, there are two "types" of halting:
     • accept, if the computation ends in some accepting state. I write $M(i, w) = 1$ to denote this
     • reject, otherwise. I write $M(i, w) = 0$ to denote this.

I have recently read on Wikipedia that the definition of the $P$ class is the following:

A language L is in P if and only if there exists a deterministic Turing machine M, such that

• M runs for polynomial time on all inputs
• For all x in L, M outputs 1
• For all x not in L, M outputs 0

https://en.wikipedia.org/wiki/P_(complexity)

I adapted the definition to my Turing machine model as follows:

A language L is in P if and only if there exists a Turing machine M, such that

• For all inputs x, $\exists \, a \in \mathbb{N} : \mathbb{T}[M,x,\varepsilon] \le |x|^a$. I write $\varepsilon$ for the empty string. By $\mathbb{T}[M,i,w]$ I mean the number of time units required in the computation of $M$ with $i$ and $w$.
• For all x in L, $M(x, \varepsilon) = 1$
• For all x not in L, $M(x, \varepsilon) = 0$

I am searching to define a complexity class where exactly the same rules of $P$ apply to both the input and the witness. Therefore, I want to define this:

A language L is in ... (insert complexity class name here) if and only if there exists a Turing machine M, such that

• For all inputs x and for all witnesses w of x, $\exists \, a \in \mathbb{N} : \mathbb{T}[M,x,w] \le |x|^a$
• For all x in L and for all witnesses w of x, $M(x, w) = 1$
• For all x not in L and for all witnesses w of x, $M(x, w) = 0$

As I see it, it would obviously be a superset of $P$ (since for all inputs $i$, we have $\varepsilon \in \{ w : w \text{ is a witness of } i \}$).

QUESTION: Did someone already propose before a complexity class that satisfies my above definition?

What I don't know is whether there is a widely-known name for this specific complexity class (as we have with $P$, $PSPACE$, $EXP$ etc.) or I should define it on my own (with some arbitrary name, say $P_{+W}$?)

Thank you for looking over my question!

P. S. I have previously found the class $ZPP$ as an almost-good candidate for the answer to my question, but because I read on Wikipedia the following:

if the algorithm is allowed to flip a truly-random coin while it is running, it will always return the correct answer and, for a problem of size n, there is some polynomial p(n) such that the average running time will be less than p(n), even though it might occasionally be much longer

https://en.wikipedia.org/wiki/ZPP_(complexity)

I have understood that the average running time (i.e., the average of all running times) will be polynomially bounded, whereas, with my class, I want all running times to be polynomially bounded, just like in $P$. Did I understand anything wrong with this?

Answer 1

First, this

For all inputs x, $\exists \, a \in \mathbb{N} : \mathbb{T}[M,x,\varepsilon] \le |x|^a$.

is wrong for the definition of P. Every terminating Turing machine will satisfy this condition. Why? Because the choice of the exponent $a$ depends on the input $x$, the time complexity can be $|x|^{|x|}$ for example.

The correct definition uses the swapped order qualifiers like $\exists a\forall x, T(x) \leq |x|^a$.

Now, the main question

• For all x in L and for all witnesses w of x, $M(x, w) = 1$
• For all x not in L and for all witnesses w of x, $M(x, w) = 0$

This is just P. You wrote:

As I see it, it would obviously be a superset of $P$ (since for all inputs $i$, we have $\varepsilon \in \{ w : w \text{ is a witness of } i \}$).

but this argument actually shows the language class in the question is a subset of P.

Think this way: you are given a Turing machine satisfying the conditions. Can you recognize the given language in polynomial time? Yes, we can simulate $M$ with the empty witness, and output the result.

It is also easy to show the language class in the question contains P because the witness can just be discarded. Therefore, the language class in the question is P.