# What complexity class is this?

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?

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.

• Thank you for your answer. I will mark it as the correct answer, but would it be possible for you to edit your answer and make a very quick math demonstration of the last two paragraphs for me? Thanks a lot! Jul 18, 2022 at 7:35
• @QwertyBoy Not sure which part you don't understand. The only argument used is that $(\forall w, P(w))$ implies $P(\varepsilon)$ for any proposition $P$. Also note that $\forall x, \forall w, P(x,w)$ iff $\forall w, \forall x, P(x,w)$ therefore it implies $\forall x, P(x, \varepsilon)$. Jul 18, 2022 at 8:20
• Thank you very much! Jul 18, 2022 at 9:31