CSP означает проблему удовлетворения ограничений.
Читая статью «Пора ли объявить победу в подсчете сложностей?» в блоге «Потерянное письмо Годеля и P = NP» они упомянули дихотомию для CSP. После некоторой ссылки, поиска в Google и википедирования, я наткнулся на теорему Ладнера : Теорема Ладнера: если , то в N P ∖ P существуют проблемы , которые...
При разработке алгоритмов аппроксимации иногда решают полуопределенную программу с последующим шагом округления. Часто используемый пример, иллюстрирующий это, - Max-Cut. (См., Например, Алгоритмы аппроксимации Vijay Vazirani.) Существуют ли хорошие образовательные источники или обзоры, выходящие...
В прошлом я реализовывал модели координации, используя SAT и регулярное удовлетворение ограничений в качестве основной рабочей силы в своих двигателях. Продолжая эту работу, я хотел бы сделать модели более интерактивными, и лучший способ, которым я это вижу, состоит в том, чтобы открыть решатель...
Фон : В оригинальной статье UGC Субхаша Хота ( PDF ) он доказывает, что UG-сложность определения того, допускает ли заданный экземпляр CSP ограничения всех форм Не-все-равные (a, b, c) по троичному алфавиту 1 - ограничений или не существует никаких заданий, удовлетворяющих 8ϵϵ\epsilonиз...
Задача обслуживания заказа (или «поддержание заказа в списке») заключается в поддержке операций: singleton: создает список с одним элементом, возвращает указатель на него insertAfter: дает указатель на элемент, вставляет новый элемент после него, возвращает указатель на новый элемент delete: дает...
Эквивалентная формулировка теоремы PCP является: Для Макса 3-SAT это -трудного различать выполнимые формулы и формулы , где не более группу фракций из пунктов являются выполнимы (для некоторого ).r r < 1NпNPNPрrrг < 1r<1r\lt 1 Существует ли какая-либо известная теорема о дихотомии, которая...
Следующий вопрос неоднократно возникал при тестировании безопасности системы или модели. Мотивация: недостатки безопасности программного обеспечения часто возникают не из-за ошибок из-за допустимых входных данных, а из-за неправильных входных данных, которые достаточно близки к допустимым входным...
Пусть - формула 2CNF, а k - неотрицательное целое число. В этой статье доказано, что проблема принятия решения о том, можно ли удалить не более k предложений, чтобы сделать φ выполнимой, задается с фиксированным параметром, где k - параметр. Мой вопрос заключается в том, есть ли какие-либо работы,...
Теорема Шефера о дихотомии показывает, что каждая задача CSP над либо разрешима за полиномиальное время, либо NP-полна. Это относится только к задачам CSP с ограниченной шириной, за исключением, например, SAT и Horn-SAT. Общие проблемы CSP с неограниченной шириной могут быть очень сложными (даже не...
Проблема N-королевы заключается в следующем: Вход: N Вывод: размещение N «ферзей» на шахматной доске NXN таким образом, чтобы никакие две королевы не лежали в одной строке, столбце или диагонали. Сделав поиск в Google по этому вопросу, я обнаружил, что многие слайды многих профессоров утверждают,...
На SODA 2006 работа Мартина Грохе и D sharp Нила Маркса «Решение ограничений с помощью дробных краевых покрытий» ( цитирование ACM ) показала, что для класса гиперграфов H с ограниченной дробной шириной гипердерева CSP ( H ) \ in ПТИМ .a´a´\acute{\rm a}HHHHHH∈PTIME∈PTIME\in PTIME Определения и т....
При фиксированном ориентированный граф (орграф) , то Проблема Решение -раскраска спрашивает , может ли входной Орграф имеет гомоморфизм к . (Гомоморфизм в - это отображение из в , сохраняющее дуги, то есть, если - дуга в , то - это дуга...