1
$\begingroup$

My book uses this definition for the Polynomial complexity class ($L$ is a language over $\{0,1\}$):

$$\mathrm{P} = \left\{L\subseteq\{0,1\}^*\;\middle|\; \begin{array}{l} \text{there exists an algorithm $A$ that decides $L$} \\ \text{in polynomial time}\end{array}\right\}\,.$$

But by this definition, don't all languages belong to the polynomial complexity class? Because if I define $A$ to be 1 for all languages, then $A$ would decide all $L$ in constant time (and therefore polynomial time), since it would return 1 immediately, meaning all languages would belong to polynomial complexity.

Why is my logic incorrect?

$\endgroup$
  • $\begingroup$ You have correctly concluded that the language containing all strings, $\Sigma^*$ belongs to P. $\endgroup$ – Pål GD Dec 5 '15 at 23:22
2
$\begingroup$

You seem to be confusing languages and strings.

An algorithm that decides a language $L$ is an algorithm whose input is a string $w$ and whose output is true if $w\in L$ and false if $w\notin L$. As such, an algorithm can only decide one language: specifically, the language $$L_A = \{w\mid A(w)=\mathrm{true}\}\,.$$

So, when you say, "then $A$ would decide all $L$", you're making a category error. An algorithm cannot possibly decide more than one language. What you've described is an algorithm that outputs true for every input: in other worse, an algorithm that decides the language $\{0,1\}^*$.

Note that $A$ decides a language by taking strings as inputs; it doesn't take languages as input and decide whether that langauge is in P.

$\endgroup$
  • $\begingroup$ Exactly what I was looking for, thank you. $\endgroup$ – fgdfgdstserg Dec 6 '15 at 0:21

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.