P class definition in Garey and Johnson's Computers and Intractability

Question

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

Answer 1

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.

Answer 2

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