Laboratory of Mathematical Logic at PDMI

Пятница, 4 ноября, комната 106. Начало в 17:30.

Докладчик: Ю. Лифшиц и Д. Павлов.

Тема: Алгоритмы для Parity Games.

Abstract

Задача определения победителя в Parity Games эквивалентна поиску ошибок в широком классе моделей программ. Про эту задачу известно, что она лежит в NP и coNP, но полиномиальный алгоритм пока не известен. В докладе мы представим уже известные (экспоненциальные) алгоритмы и наш новый алгоритм (тоже экспоненциальный).

Parity Game заключается в следующем: есть двудольный ориентированный граф, в вершинах стоят целые числа. Двое игроков по очереди двигают фишку по вершинам до бесконечности. Среди чисел, встретившихся на траектории фишки бесконечное число раз берется наибольшее. Если он четное -- выигрывает первый, нечетное -- второй. Требуется по данному графу и стартовой вершине определить, кто выигрывает при правильной игре.