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

68 Views Asked by At

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