Доказательство PSPACE-полноты задачи конкурентного размещения
Утверждение (9.10) открывает путь в мир игровых задач. Мы воспользуемся этой связью для доказательства PSPACE-полноты задачи конкурентного размещения.
(9.11) Задача конкурентного размещения является PSPACE-полной.
Имеется экземпляр конкурентной задачи 3-SAT, определяемый формуло.
Каждое условие Cj имеет длину 3 и может быть записано в виде Cj = tj1 Ҏ tj2 Ҏ tj3. Как и прежде, будем считать, что количество переменных n нечетно. Также будем полагать (по естественным причинам), что никакое условие не содержит литерал одновременно с его отрицанием; в конце концов, такое условие автоматически выполняется любым логическим присваиванием.
Мы должны показать, как закодировать эту логическую структуру в графе, лежащем в основе задачи конкурентного размещения.
Экземпляр конкурентной задачи 3-SAT можно закодировать в следующем виде. Игроки поочередно выбирают значения в логическом присваивании, начиная и заканчивая игроком 1; в конце игрок 2 выигрывает, если он выберет условие Cj, котором ни одному литералу не было задано значение 1. Игрок 1 выигрывает, если игроку 2 это сделать не удастся.
В такой формулировке нам хотелось бы закодировать экземпляр задачи конкурентного размещения: игроки поочередно делают фиксированное количество ходов, и в конце существует вероятность того, что игрок 2 победит.
Но в общей формулировке задача конкурентного размещения выглядит намного более открытой. Если игроки в конкурентной задаче 3-SAT должны задавать по одной переменной в строгом порядке, игроки в задаче конкурентного размещения могут перемещаться по всему графу, выбирая любые узлы на свое усмотрение.
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу