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