После выпуска библиотеки AIGER для обработки и инвертирования графов где-то в 2006 году (я думаю), некоторые схемы SAT решатели были выпущены в 2006-2008 годах, и в нескольких гонках / соревнованиях SAT были треки AIG. Однако с тех пор кажется, что основное внимание было уделено либо SMT, либо улучшению клаузальных SAT решателей.
Интуитивно мне кажется, что сосредоточение на схеме SAT имеет большой смысл: многие, если не большинство проблем, более естественно выражаются в схеме SAT, чем в CNF; схемы предоставляют структурную информацию, которая не может быть преобразована обратно из CNF, но схемы всегда могут быть преобразованы в CNF; и, по крайней мере, промышленно значимая область логического синтеза представляется особенно подходящей для AIG.
Итак, что случилось? Получилось ли так, что дополнительная структурная информация не помогает решателям? SAT на основе AIG решал неудачный эксперимент?
источник
Ответы:
Есть много разных точек зрения на ваш вопрос. в целом согласился с вашей предпосылкой, что рассмотрение «структурной информации» в формулировке SAT должно быть отличной областью исследований.
SAT, закодированный в CNF, был стандартом на протяжении десятилетий. он был укреплен в начале-середине 1990-х годов в формате / соревнованиях DIMACS .
что технически означает «структурная информация»? может быть трудно формально закрепить эту концепцию и избежать почти тавтологических кругов. на самом деле нет никакой разницы между кодировкой SAT CNF и другими кодировками, которые сохраняют структуру сети. это воплощено в понятиях «раздел / график переменных», которые, как правило, используют очень многие SAT-решатели. другими словами, в некотором смысле каждый значимый решатель SAT использует «структурную информацию» .
да, новые направления в исследованиях были сосредоточены на ASP и SMT- решениях, которые практически фактически воплощают «структурную информацию», о которой вы спрашиваете.
Преобразование Цейтина легко преобразует схему в SAT в P время / пространство для ввода в стандартный решатель SAT. он предположительно широко используется во многих контекстах, особенно в контекстах схем EE.
Есть некоторые довольно изолированные исследования, как правило, в тех направлениях, о которых вы упоминаете, но, к сожалению (опять же, вместе с вашей предпосылкой), они никогда не развивались в направлении исследований. не думаю, что это связано с отсутствием потенциала, но больше человеческих факторов. две любимые статьи [1] [2], другая - это рассмотрение конкретных примеров из таких областей, как «промышленные образцы» или «электротехника», в которых проводятся некоторые специализированные исследования.
Пуристы CS иногда склонны избегать психологических / социологических соображений во всех математических абстракциях, но разумно это все еще фактор в информатике . Вы спрашиваете о направлениях исследований, которые основаны на человеческих психологических факторах. возможно, здесь происходит какой-то эффект уличного освещения, он же «низко висящий фрукт». Кто-то может сказать / подумать, что даже сейчас, несколько десятилетий назад, алгоритмическое исследование SAT находится в зачаточном состоянии, так что больших вопросов, таких как P против NP, кажется, нигде не видно, и, возможно, существующие исследования, хотя они и остаются существенными, все еще просто «процарапывают поверхность» ,
[1] Разложение проблем выполнимости или Использование графиков для лучшего понимания проблем выполнимости , Herwig 2006 (83pp)
[2] Скованность ножа лезвием Уолша 1998
источник