Definition of complexity classes?

Question

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?

Answer 1

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.