Складні класи, пов'язані з пам'яттю. Теорема Севіча. PSPACE-повнота. Обчислення на логарифмічній пам'яті. NL-повнота
Питання: Складні класи, пов'язані з пам'яттю. Теорема Севіча. PSPACE-повнота. Обчислення на логарифмічній пам'яті. NL-повнота Складні класи, пов'язані з пам'яттю Функція ?: N → N називається функцією, що конструктується за пам’яттю, якщо існує машина Тьюринга, яка по входу 1? обчислює ?(?), використовуючи пам'ять ?(?(?)). Нехай ?(?) – неспадна функція. Класом DSPACE(?(?)) називається клас мов, які можна розпізнати на детермінованій машині Тьюринга, на будь-якому вході довжини ?, що використовує ?(?(?)) осередків на робочих стрічках. Нехай ?(?) - неспадна функція. Класом NSPACE(?(?)) називається клас мов, які можна розпізнати на недетермінованій машині Тьюринга, на будь-якому вході довжини ?, що використовує ?(?(?)) осередків на робочих стрічках (при будь-яких результатах недетермінірованного вибору).