Смутно о классах сложности?

Question

Моя книга использует это определение для полиномиального класса сложности (L представляет собой бинарный язык):

Но по этому определению, не все языки принадлежат к классу полиномиальной сложности? Поскольку, если я определяю A как 1 для всех языков, тогда A будет решать все L в постоянное время (и, следовательно, полиномиальное время), так как он немедленно возвращает 1, что означает, что все языки будут принадлежать полиномиальной сложности.

Почему моя логика неверна?

Answer 1

В моем понимании «A решает L» означает, что алгоритм A решает, принадлежит ли данному слову w L. В этом предположении, что A всегда возвращает true, не имеет смысла, поскольку этот алгоритм может решить только язык, содержит все возможные слова. Это не было бы алгоритмом для любого другого языка.