такий хід білих, що, як би не зіграли чорні, білі виграють.
: безлічі для ігор з 2 ходів. Іншими словами, це безлічі виду
В В
: безлічі для ігор з ходів (залежно від парності останніми ходять або чорні, або білі). Іншими словами, це безлічі виду
В
(якщо парне, то,, якщо непарне, то,).
: безлічі для ігор з ходів (залежно від парності останніми ходять або чорні, або білі). Іншими словами, це безлічі виду
В
(якщо парне, то,, якщо непарне, то,).
В
Класи і взаємно додатковими:,.
Теорема 4.1 (Лаутеман [35 <# "18" src = "doc_zip972.jpg"/>.
Доказ. Оскільки клас BPP замкнутий щодо доповнень, досить показати, що. p> Для цього потрібно навчитися формулювати властивість "безліч містить багато елементів" з використанням кванторів існування та загальності. Ми зробимо це, припускаючи, що розглядаються підмножини деякої кінцевої групи. Нехай - Група, а - підмножина. Властивість, якою ми будемо відрізняти великі безлічі від малих, полягає в тому, що деяким кількістю зрушень безлічі можна покрити всю групу
(4.1)
Щоб вибрати відповідне значення , потрібно знайти випадки, коли (4.1) завідомо виконується, і коли свідомо не виконується.
Якщо
(4.2)
умова (4.1) свідомо неправдиво.
Умова (4.1) завідомо істинно, якщо для випадкових незалежних ймовірність події більше 0. Іншими словами, . Ймовірність того, що випадковий зсув не покриває (не містить) деякий фіксований елемент, дорівнює з очевидних причин . Ймовірність того, що випадкових зрушень не покривають фіксований елемент, дорівнює (покриття різними зсувами - незалежні події). Оскільки покривається елементів, ймовірність події не більш (ймовірність об'єднання подій не більш суми ймовірностей цих подій). Отже, при
(4.3)
умова (4.1) завідомо виконується.
Розглянемо тепер деякий мову. Для нього, як пояснювалося вище, можна знайти полиномиально вичіслімих предикат і поліном такі, що число, де, розрізняє слова, що належать мови (для них воно більше), і слова, мови не належать (для таких слів це число менше). Параметр ми виберемо пізніше, зараз відзначимо, що його величина може бути експоненціально мала, як пояснювалося в лекції 3 <# "14" src = "doc_zip1000.jpg"/> довжини так, щоб твір і звернення елемента в цій групі були полиномиально вичіслім...
