и кожного разу саме цей проміжок.
Завдання 4.1. Доведіть, що клас мов, які розпізнаються недетермінованими машинами, що працюють на пам'яті , міститься в класі мов, які розпізнаються детермінованими машинами, що працюють на пам'яті .
В якості слідства теореми 4.2 отримуємо включення всіх визначених вище класів , в клас . Взаємне співвідношення цих класів можна зобразити діаграмою включень, показаної нижче. На цій діаграмі від більшого класу до меншого можна пройти, рухаючись по стрілках. Внизу розташовується клас , що відповідає ігор з 0 ходів, потім йдуть доповнюють один одного класи, що відповідають іграм з кінцевим числом ходів (для одного ходу це NP і co-NP, для двох ходів - і і т.д.). Завершується ця діаграма класом , який визначається довільними іграми з одним природним умовою - час гри має бути полиномиально обмежено розміром вхідного слова. Ми вже довели всі включення, зображені на цій діаграмі. Ні про одне з включень, наступних з цієї діаграми, невідомо, чи є воно суворим. Бути може, скажімо, . З іншого боку, можливо й так, що , де позначає (не розглядалося нами) клас мов, вичіслімих за експоненціальне час . Втім, найбільш популярна гіпотеза про те, що всі включення, зображені на діаграмі - строгі.
В
Малюнок 4.1: Схема PSPACE
Завдання 4.2. Машина Тюрінга з оракулом - це МТ з додатковою оракульной стрічкою, куди вона (машина) може записувати слова, а потім за один такт роботи перевіряти, чи належить записане на оракульной стрічці слово мови < span align = "justify">. По двох сложностним класам і можна визначити клас таких мов, які розпізнаються машинами з класу з оракулами з .
Доведіть, що .
У класі існують повні задачі (щодо поліноміальної сводимости). Найпростіший варіант виходить застосуванням попередньої теореми.
Завдання . Здається предикатом
є істинна булева формула з кванторами (True Quantified Boolean Formula), тобто формула виду
В
де , - деяка логічна формула, а
