Классы сложности.

1? – означает: выполняется ли равенство NP-time = P-time или нет. Ответ на этот вопрос неизвестен и стоит $1000000.

2? – означает: выполняется ли равенство NP-space= Np-time или нет (то есть существуют ли задачи, которым хватает полиномиальной памяти, но за полиномиальное время даже на НДМТ их решить нельзя). Ответ на этот вопрос так же неизвестен.

3?- означает: существуют ли задачи, которые нельзя решить, используя только полиномиальную память. Ответ на этот вопрос дается

Теоремой 5.10

Существует задача( задача непустоты дополнения полурасширенного выражения), которая решаема. Но для ее решения требуется больше чем

памяти, где - константа, сколь угодно большая. Тем более эта задача не решаема за полиномиальное время с использованием полиномиальной памяти.

Без доказательства.

4? – означает: существуют ли неразрешаемые задачи? Ответ на данный вопрос дается в Разделе 6.