0
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Raphael Aug 2 '12 at 8:35
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – aemxdp Aug 2 '12 at 8:48

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.