Формально, элементами класса

являются языки. Пусть

- конечный алфавит(то есть конечное непустое множество), содержащий по крайней мере 2 элемента, и

- множество всех конечных слов в алфавите

. Язык в алфавите

--- подмножество

. С любой машиной Тьюринга

связан ее входной алфавит

. Для любого слова

из

существует вычисление машины

на входе

. (Машина Тьюринга и вычисление определены формально в приложении.) Будем говорить, что

принимает слово

, если в конце вычисления машина находится в принимающем состоянии. Таким образом,

не принимает

, если вычисление завершается в отвергающем состоянии машины, или если процесс вычисления не завершается. Язык, распознаваемый машиной

(обозначается

) - это язык в алфавите

, определяемый как

. Обозначим

количество шагов вычисления

на входе

(см. приложение). Если вычисление не завершается, то

. Для

обозначим

время вычислений на слове длины

в худшем случае, то есть

, где

- множество всех слов длины

в алфавите

. Будем говорить, что машина

работает полиномиальное время, если существует

такое, что для любого

верно

. Теперь мы можем определить класс языков

как

Обозначение

расшифровывается как "nondeterministic polynomial time", поскольку этот класс изначально определялся в терминах недерминированных машин. Однако сейчас обычно дается эквивалентное определение, использующее понятие проверяющего отношения - бинарного отношения

для некоторых конечных алфавитов

и

. Каждому такому отношению мы ставим в соответствие язык в алфавите

определяемый как

где символ

не принадлежит языку

. Будем говорить, что

проверяется за полиномиальное время, если

. Определим класс языков

следующим образом: язык

в алфавите

принадлежит

если и только если существует

и проверяемое за полиномиальное время бинарное отношение

такие, что для любого слова

где

и

- длины слов

и

соответственно.
Формулировка проблемы. Верно ли, что

?