2
$\begingroup$

I'm reading right now Computers and Intractability by Garey and Johnson. I've found the definition of PTIME complexity class a little strange. This is how it looks:

Let $\Sigma = \{ 0,1\}$. By $\Sigma^{*}$ we denote the set of all finite strings created from symbols from $\Sigma$. If a computation on a Deterministic Turing Machine with input $x \in \Sigma^{*}$ ends in $q_{y}$ (yes-state), it means that TM accepts this input. Language $L_{M}$ recognised by the machine $M$ is given by:

$L_{M} = \{ x \in \Sigma^{*} :$ $M$ accepts $x \}$.

Time complexity function is given by:

$T_{M} = max\{ m : $ there is an $x \in \Sigma^{*}$, with $|x| = n$, such that the computation of $M$ on input $x$ takes time $m$$\}$.

We call program $M$ a polynomial time DTM program if there exists a polynomial $p$ such that, for all $n \in \mathbb{Z}^{+}$, $T_{M}(n) \leq p(n)$.

Then they give such $P$ class definition:

$P = \{ L :$ there is a polynomial time DTM program $M$ for which $L=L_{M} \}$


Does this mean that their P complexity class contains only languages that are composed of yes-instances, i.e. languages recognised by $M$, consisted of $x$ strings such that $M$ always halts in accepting state for every of them as an input? What about input that also causes halting, but in rejecting state $q_{n}$? Shouldn't these be also in PTIME?

Do I understand this correctly? If yes, why they decided to define P class in such way?

P.S. Maybe that matters, I have the first edition of the book (1979).

$\endgroup$
1
$\begingroup$

The definition given is the standard one. Before reading the rest of this answer, I recommend that you carefully go over the definition again. A lot of what you're asking is "What does the definition say?" and you'll probably understand it better if you figure it out yourself. The rest of your question is, "Why did we choose that definition?"


The definition is equivalent to the following. A Turing machine $M$ "runs in polynomial time" if there is some polynomial $p$ such that $M$ halts in at most $p(n)$ steps for all inputs of length $n$. A language is in P if it is the set of strings accepted by some Turing machine that runs in polynomial time.

Does this mean that their P complexity class contains only languages that are composed of yes-instances, i.e. languages recognised by $M$, consisted of $x$ strings such that $M$ always halts in accepting state for every of them as an input?

Yes, that's what the definition says. It also says a little more: the language recognised by $M$ doesn't include any of the "no" instances.

What about input that also causes halting, but in rejecting state $q_{n}$?

If a machine runs in polynomial time, it halts for all inputs. Thus, for any given input, the machine either accepts or rejects. The whole point is that the Turing machine tells you exactly which inputs are in the language and exactly which inputs are not. If the machine rejects an input, that input isn't in the language.

Shouldn't these be also in PTIME?

This is a category error. P is a class of languages, not inputs.

However, you might be thinking of the following. We could also define a language that is the set of strings rejected by some Turing machine that runs in polynomial time. Perhaps you're wondering why that language isn't in P? Well, it is, because it's also the set of strings accepted by some polynomial-time Turing machine. Just take the machine that defines the language by rejecting and modify it so that every instruction "go to the accepting state" becomes "go to the rejecting state" and vice-versa. Now you have a Turing machine that defines the language you're interested in, but defines it by acceptance.

$\endgroup$
  • $\begingroup$ Thank you very much, it's much more clear for me now. Although I still do not understand why this definition omits such languages: a language is in P if it is the set of strings rejected by some Turing machine that runs in polynomial time. From what I understand, definition from Wikipedia considers also such languages to be in P (en.wikipedia.org/wiki/P_(complexity)): 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 $\endgroup$ – John Liewelson Dec 7 '17 at 11:08
  • $\begingroup$ That's the same definition as in Garey and Johnson-- "outputs 1" means "accepts" and "outputs 0" means "rejects". But I'll add a little to the answer because there's another thing you might be thinking of. (Easier to just write it, rather than try to carry out a conversation in the comments.) $\endgroup$ – David Richerby Dec 7 '17 at 11:11
  • $\begingroup$ Nota bene, @JohnLiewelson: "the set of strings rejected by some Turing machine that runs in polynomial time" -- this is basically the idea behind co-P. Since co-P = P, this is rather boring. However, things become more interesting when looking at NP -- we don't know whether co-NP = NP! Figuring out why there's a different is highly educational. $\endgroup$ – Raphael Dec 7 '17 at 11:16
  • $\begingroup$ >Just take the machine that defines the language by rejecting and modify it so that every instruction "go to the accepting state" becomes "go to the rejecting state" and vice-versa. >this is basically the idea behind co-P This is exactly what I was lacking, thank you both very much! $\endgroup$ – John Liewelson Dec 7 '17 at 12:08
0
$\begingroup$

As you remark, inputs that halt in a rejecting state should also take polynomial time for $M$ to be a polynomial-time DTM.

Note that the running time $T_M$ as defined in your question is indeed defined as the maximum over the running time of Turing machine $M$ for any size-$n$ input (namely, the running time for any $x \in \Sigma^*$ with $|x| = n$).

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