# Problem with the definition of P

In "Introduction to Algorithms: 3rd Edition" there is Theorem 34.2, which states

$P = \{ L \mid L \text{ is accepted by a polynomial-time algorithm} \}$

"Accepted in polynomial-time" is defined by:

$L$ is accepted in polynomial time by an algorithm $A$ if it is accepted by $A$ and if in addition there exists a constant $k$ such that for any length-n string $x\in L$, algorithm $A$ accepts $x$ in time $O(n^k)$.

"Accepted" is defined by:

The language accepted by an algorithm $A$ is the set of strings $L = \{ x \in \{0,1\}^* \mid A(x) = 1 \}$, that is, the set of strings that the algorithm accepts.

But what if we take $k = 0$, and algorithm $A(\cdot) = 1$, which just returns 1 for everything? Wouldn't that mean, that $P$ is just class of all languages?

• Note that "accepted in polynomial time" says "there exists a $k$", so you are not allowed to fix $k$. That said, $\Sigma^*$ (which is accepted by $A(x)=1$) is certainly in $P$, which you have proven. – Raphael Aug 2 '12 at 8:35

No this means, that the language $L$ that contains all possible words ($L=\Sigma^*$) is in $P$. In other words, no matter what your input is, the algorithm accepts. And the corresponding language is of course (trivially) decidable in polynomial time.

To clarify things: A language is a set of words (the words are considered as encodings of the yes-instances of a problem). A complexity class is a set of languages - so it is a set of sets. When a language $L$ contains all possible words, it doesn't mean that a complexity class that contains $L$, contains all languages.

• Ah, thank you. My misunderstanding came from subconsciously thinking of language accepted by A as any set of words accepted by A, and not set of all such words. – aemxdp Aug 2 '12 at 8:48