их (наприклад, в якості групової операції візьмемо покомпонентное додавання по модулю два). Запишемо наступне-умова
В
Іншими словами, розглядаємо таку гру: білі своїм ходом називають слів (елементів групи), а чорні - один елемент, який, за їх думку, не покритий зрушеннями безлічі на слова, названі білими.
Умова (4.2) в цьому випадку має вигляд, а умова (4.3):. Ці умови виконуються при відповідному виборі параметрів. Можн про взяти порядку і порядку.
Зауваження 4.1. Мається міркування, яке "показує", що час обчислення функцій з класу BPP можна зробити, мабуть, менше для будь-кого. Ідея полягає в тому, щоб використовувати генератори псевдовипадкових чисел. Такий генератор по набору бітів довжини будує набір довжини, де. Якщо при цьому вибирати короткі набори випадково, то довгі набори будуть розподілені так, що обчислювальний пристрій з обмеженими ресурсами (наприклад, поліноміальна машина Тьюринга) не зможе відрізнити їх від по-справжньому випадкових. Це пояснення замінює точне визначення псевдослучайного генератора, яке нам не знадобиться. p> Чи існують селестічні генератори, невідомо. Їх свідомо немає, якщо. Але в цьому випадку. p> Якщо ж і є селестічні генератори, то можна знаходити за вказаний вище час значення функції, обчислюючи значення предиката з опр. 3.2 тільки для псевдовипадкових. p> Залишається "слабкий" дефект в цьому міркуванні: воно не проходить при та відсутності псевдовипадкових генераторів. Така ситуація вважається малоймовірною. br/>
Тема 4.2 Клас PSPACE
Як вже говорилося, в цей клас потрапляють ті функції, які можуть бути обчислені на МТ, що використовує пам'ять, обмежену поліномом від довжини вхідного слова. Клас PSPACE також можна описати, використовуючи гри. p align="justify"> Теорема 4.2. тоді і тільки тоді, коли існує така гра з поліноміальним від довжини вхідного слова числом ходів і полиномиально вичіслімих результатом, що Б має виграшну стратегію .
Доказ Покажемо, що мова, який визначається грою, належить . Нехай число ходів обмежена . Визначимо по індукції набір машин Тьюринга для . Кожна по заданому початку гри довжини визначає наявність виграшної стратегії у Б. Останньою в цьому ряду машині потрібно просто обчислити предикат . Машина перебирає всі можливі варіанти -го ходу і консультується з з приводу остаточних результатів гри. Її оцінка гри складається дуже просто: якщо поточний хід у Б, то достатньо ...
