1
$\begingroup$

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?

$\endgroup$

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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! $\endgroup$
    – Qwerty Boy
    Jul 18 at 7:35
  • $\begingroup$ @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)$. $\endgroup$
    – pcpthm
    Jul 18 at 8:20
  • $\begingroup$ Thank you very much! $\endgroup$
    – Qwerty Boy
    Jul 18 at 9:31

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.