'

Методы автоматизации доказательства NP-полноты двумерных локально зависимых задач

Понравилась презентация – покажи это...





Слайд 0

Методы автоматизации доказательства NP-полноты двумерных локально зависимых задач Дворкин М. Э. Научный руководитель: Корнеев Г. А., к. т. н., доцент КТ СПбГУ ИТМО dvorkin@rain.ifmo.ru


Слайд 1

Двумерные локально зависимые задачи Вход: поле h?w Вопрос: существует ли заполнение? Корректность заполнения = проверка квадратов s?s Примеры: Головоломки Сапер Какуро (CROSS SUM) Замощение данным набором полимино (p,q)-замощение 2 Автоматизация доказательства NP-полноты двумерных задач Дворкин М. Э.


Слайд 2

Применение устройств «На языке задачи L» выражается известная NP-полная задача Используются «устройства» (gadgets) и провода, соединяющие их Устройства могут быть сложны 3 Автоматизация доказательства NP-полноты двумерных задач Дворкин М. Э.


Слайд 3

Постановка задачи Автоматизация построения устройств с заданной функциональностью Описание наборов устройств, достаточных для доказательства NP-полноты Программная реализация Применение для доказательства NP-полноты конкретных задач N-CROSS SUM 4 Автоматизация доказательства NP-полноты двумерных задач Дворкин М. Э.


Слайд 4

Сведение 1-in-3 SAT к L Задача 1-in-3 SAT: Вход: конъюнкция из предикатов R(A, B, C) Вопрос: выполнима ли конъюнкция? Удобна, поскольку истинность конъюнкций проверяется независимо 5 Автоматизация доказательства NP-полноты двумерных задач Дворкин М. Э.


Слайд 5

Одинарные и двойные провода Провод придумывается человеком, зачастую — просто Устройство «создание провода» не всегда существует Рассматриваются двойные провода: «в фазе» «в противофазе» 6 Автоматизация доказательства NP-полноты двумерных задач Дворкин М. Э.


Слайд 6

Набор устройств для двойных проводов «Создание» «Валидатор» «Одинарный провод» «Перекрещивание» «1 из 3» «2 из 3» 7 Автоматизация доказательства NP-полноты двумерных задач Дворкин М. Э.


Слайд 7

Динамическое программирование по профилю Профиль — вертикальный «срез» поля, содержит всю необходимую информацию для дальнейшей обработки поля Прямой профиль Проще для понимания Громоздкий переход, большая таблица переходов Изломанный профиль Их число больше Таблица переходов меньше 8 Автоматизация доказательства NP-полноты двумерных задач Дворкин М. Э.


Слайд 8

Подход «перебор всех полей» Перебрать все поля, O(|A|hw) Для каждого проверить, является ли оно искомым устройством, O(nhwp|B|) Итого: O(|A|hwnhwp|B|) Улучшение: для разных полей не обрабатывать общие префиксы Время работы: O(|A|hwnp|B|) 9 Автоматизация доказательства NP-полноты двумерных задач Дворкин М. Э.


Слайд 9

Метадинамическое программирование Рассмотрим два поля после обработки первых i клеток. Что если все совпадает? Метапрофиль — множества достижимых профилей для каждого набора булевых значений входных проводов После обработки i-й клетки все поля с одинаковыми метапрофилями можно отождествить 10 Автоматизация доказательства NP-полноты двумерных задач Дворкин М. Э.


Слайд 10

Метадинамическое программирование O(min(|A|hwnp|B|, |A||B|nphw2np)) Критична высота рассматриваемого поля Если после обработки столбца то же множество метапрофилей, что и до нее, можно остановиться Для каждого метапрофиля хранится одно поле-представитель (самое «красивое») 11 Автоматизация доказательства NP-полноты двумерных задач Дворкин М. Э.


Слайд 11

Задача (2,3)-замощения 12 Автоматизация доказательства NP-полноты двумерных задач Дворкин М. Э.


Слайд 12

Задача 4-CROSS SUM (открытый вопрос) 13 Автоматизация доказательства NP-полноты двумерных задач Дворкин М. Э.


Слайд 13

Задача 4-CROSS SUM (открытый вопрос) 14 Автоматизация доказательства NP-полноты двумерных задач Дворкин М. Э.


Слайд 14

Спасибо за внимание Есть ли вопросы? 15 Автоматизация доказательства NP-полноты двумерных задач Дворкин М. Э.


×

HTML:





Ссылка: