иконання нерівності . При такому співвідношенні між і завжди знайдеться випадкове слово, для якого немає помилок ні за яких .
Дійсно, згадаємо наочне тлумачення BPP, дане після теореми 3.1. Якщо частка слів , на яких відбувається помилка, для кожного вбирається , то частка тих слів , на яких відбувається помилка хоча б для одного , вбирається . Значить, знайдуться й такі , на яких немає помилок ні при якому .
Це типове неконструктивну доказ існування. Ми доводимо, що ймовірність того, що об'єкта з потрібними властивостями не існує, менше 1. Але це і означає, що хоча б один такий об'єкт існує. p align="justify"> Розділ № 4. Ієрархія сложностних класів
Тема 4.1 Суть сложностних класів
Нагадаємо, що ми ототожнюємо мови і предикати, як описано в лекції 1 <# "16" src = "doc_zip902.jpg"/> означає.
Визначення 4.1. Нехай - деякий клас мов. Клас доповнень складають доповнення до всіх мов з. Формально
В
Безпосередньо з визначень класів випливає, що,,.
Ігри, в які грають машини.
Розглянемо гру, в яку грають два гравці, будемо їх називати білі (Б) і чорні (Ч). Гравцям повідомляється деяке слово, і вони роблять ходи по черзі (- перший хід білих, - перший хід чорних і т.д.). Кожен хід може бути описаний словом довжини, де - деякий поліном. Гра завершується після деякого, заздалегідь заданого, числа ходов1) <# "22" src = "doc_zip917.jpg"/>, істинність якого означає, що виграли білі (нічиїх не буває, так що хибність означає, що виграли чорні). Предикат залежить від вихідного слова і ходів, зроблених гравцями: - білими, - чорними. Оскільки замкнутий щодо доповнень, предикат, який стверджує виграш чорних, також належить. p> Відсутність нічиїх і кінцівку числа ходів гарантують при заданому існування виграшної стратегії або для білих, або для чорних. (Формальне доказ легко виходить індукцією по числу ходів.) Тому кожній грі можна зіставити два взаємно додаткових безлічі
В
Багато сложностние класи можна визначити як безлічі (або), відповідні тим чи іншим видам ігор. Наприклад, отримуємо такі класи. p>: безлічі (як і, втім) для ігор, в яких ніхто не робить ходів.
: безлічі для ігор, в яких білі роблять 1 хід. Іншими словами, це безлічі виду
В
: безлічі для ігор, в яких білі роблять 1 хід. Іншими словами, це безлічі виду
В
: безлічі для ігор з 2 ходів: 1 хід білих, 1 хід чорних. Іншими словами, це безлічі виду
В
Словами це можна сказати так: є ...
