✖


Jump to content

SAT-решатель

    Add links

    В информатике и формальных методах решатель SAT представляет собой компьютерную программу , целью которой является решение проблемы логической выполнимости . При вводе формулы для логических переменных, таких как «( x или y ) и ( x or not y )», решатель SAT выводит, является ли формула выполнимой , что означает, что существуют возможные значения x и y , которые делают формулу истинной. не существует , или невыполнимо, что означает, что таких значений x и y . В этом случае формула выполнима, если x истинно, поэтому решатель должен вернуть «выполнимо». С момента появления алгоритмов SAT в 1960-х годах современные решатели SAT превратились в сложные программные артефакты , включающие большое количество эвристик и оптимизаций программ для эффективной работы.

    Согласно результату, известному как теорема Кука – Левина , булева выполнимость является NP-полной в целом проблемой. В результате известны только алгоритмы с экспоненциальной сложностью в худшем случае. Несмотря на это, в 2000-х годах были разработаны эффективные и масштабируемые алгоритмы SAT, которые способствовали значительному прогрессу в способности автоматического решения задач, включающих десятки тысяч переменных и миллионы ограничений. [1]

    Решатели SAT часто начинают с преобразования формулы в конъюнктивную нормальную форму . Они часто основаны на основных алгоритмах, таких как алгоритм DPLL , но включают в себя ряд расширений и функций. Большинство решателей SAT включают тайм-ауты, поэтому они завершат работу в разумные сроки, даже если не смогут найти решение с выходным сигналом типа «неизвестно». Часто решатели SAT не просто предоставляют ответ, но могут предоставить дополнительную информацию, включая пример задания (значения x , y и т. д.) в случае, если формула выполнима, или минимальный набор невыполнимых предложений, если формула невыполнима.

    Современные решатели SAT оказали значительное влияние на такие области, как проверка программного обеспечения , анализ программ , решение ограничений , искусственный интеллект , автоматизация электронного проектирования и исследование операций . Мощные решатели легко доступны в виде бесплатного программного обеспечения с открытым исходным кодом и встроены в некоторые языки программирования, например, предоставляя решатели SAT в качестве ограничений в программировании логики с ограничениями .

    Обзор

    [ редактировать ]
    Основная статья: Проблема логической выполнимости

    Булева формула — это любое выражение, которое можно записать с использованием логических (пропозициональных) переменных x, y, z,... и логических операций AND, OR и NOT. Например,

    ( x И y ) ИЛИ ( x И (НЕ z ))

    Присваивание состоит из выбора для каждой переменной значения ИСТИНА или ЛОЖЬ. Для любого присваивания v может быть вычислена булева формула, которая принимает значение true или false.Формула является выполнимой, если существует присваивание (называемое удовлетворяющим присваиванием ), для которого формула имеет значение true.

    Проблема булевой выполнимости — это проблема принятия решения , которая требует при вводе булевой формулы определить, выполнима ли формула или нет. Эта задача является NP-полной .

    Решатели DPLL

    [ редактировать ]
    Основная статья: алгоритм DPLL

    Решатель DPLL SAT использует систематическую процедуру поиска с возвратом для исследования (экспоненциального размера) пространства назначений переменных в поисках удовлетворяющих назначений. Базовая процедура поиска была предложена в двух основополагающих статьях в начале 1960-х годов (см. ссылки ниже) и теперь обычно называется алгоритмом Дэвиса-Патнэма-Логеманна-Лавленда («DPLL» или «DLL»). [2] [3] Многие современные подходы к практическому решению SAT основаны на алгоритме DPLL и имеют одну и ту же структуру. Часто они повышают эффективность только определенных классов задач SAT, таких как случаи, возникающие в промышленных приложениях, или случайно сгенерированные экземпляры. [4] Теоретически для семейства алгоритмов DPLL доказаны экспоненциальные нижние оценки. [ нужна ссылка ]

    Решатели CDCL

    [ редактировать ]
    Основная статья: Изучение предложений, основанное на конфликте

    Современные решатели SAT (разработанные в 2000-х годах) бывают двух видов: «управляемые конфликтами» и «прогнозирующие». Оба подхода произошли от DPLL. [4] Решатели, управляемые конфликтами, такие как обучение предложений, управляемое конфликтами (CDCL), дополняют базовый алгоритм поиска DPLL эффективным анализом конфликтов, обучением предложений, обратным переходом , формой распространения единиц с «двумя наблюдаемыми литералами» , адаптивным ветвлением и случайным перезапускается. Эмпирически было показано, что эти «дополнительные элементы» к основному систематическому поиску необходимы для обработки больших экземпляров SAT, возникающих при автоматизации проектирования электроники (EDA). [5] По состоянию на 2019 год большинство современных решателей SAT основаны на платформе CDCL. [6] Хорошо известные реализации включают Chaff [7] и ГРАСП . [8]

    Упреждающие решатели имеют особенно усиленные сокращения (выходящие за рамки распространения единичных предложений) и эвристики, и они, как правило, более эффективны, чем решатели, управляемые конфликтами, на сложных экземплярах (в то время как решатели, управляемые конфликтами, могут быть намного лучше на больших экземплярах, которые на самом деле имеют простой экземпляр внутри). [ нужна ссылка ]

    Управляемый конфликтами MiniSAT, который был относительно успешным на конкурсе SAT 2005 года, имеет всего около 600 строк кода. Современный решатель Parallel SAT — ManySAT. [9] Он может добиться сверхлинейного ускорения решения важных классов задач. Примером упреждающих решателей является March_dl, получивший приз на конкурсе SAT 2007 года. Решатель CP-SAT от Google, входящий в состав OR-Tools , завоевал золотые медали на соревнованиях по ограниченному программированию Minizinc в 2018, 2019, 2020 и 2021 годах.

    Определенные типы больших случайных выполнимых примеров SAT могут быть решены путем распространения опроса (SP). [ нужна ссылка ] В частности, в приложениях для проектирования и проверки аппаратного обеспечения выполнимость и другие логические свойства данной пропозициональной формулы иногда определяются на основе представления формулы в виде диаграммы двоичных решений (BDD).

    Разные решатели SAT найдут разные случаи легкими или трудными, и некоторые преуспевают в доказательстве невыполнимости, а другие в поиске решений.Все это поведение можно увидеть в конкурсах по решению SAT. [10]

    Параллельное решение SAT

    [ редактировать ]

    Решатели для параллельного SAT делятся на три категории: алгоритмы портфолио, алгоритм «разделяй и властвуй» и параллельного локального поиска алгоритмы . При параллельных портфелях одновременно работают несколько разных решателей SAT. Каждый из них решает копию экземпляра SAT, тогда как алгоритмы «разделяй и властвуй» разделяют задачу между процессорами. Существуют разные подходы к распараллеливанию алгоритмов локального поиска.

    Международное соревнование по решению SAT имеет параллельный курс, отражающий последние достижения в параллельном решении SAT. В 2016 году [11] 2017 [12] и 2018 год, [13] тесты проводились в системе с общей памятью с 24 вычислительными ядрами , поэтому решатели, предназначенные для распределенной памяти или многоядерных процессоров, могли не сработать.

    Портфолио

    [ редактировать ]

    В общем, не существует решателя SAT, который бы работал лучше, чем все другие решатели, при решении всех задач SAT. Алгоритм может хорошо работать в случаях проблем, с которыми сталкиваются другие, но в других случаях он будет работать хуже. Более того, учитывая экземпляр SAT, не существует надежного способа предсказать, какой алгоритм решит этот экземпляр особенно быстро. Эти ограничения мотивируют подход параллельного портфеля. Портфолио — это набор разных алгоритмов или разных конфигураций одного и того же алгоритма. Все решатели в параллельном портфеле работают на разных процессорах для решения одной и той же задачи. Если один решатель завершает работу, решатель портфеля сообщает, что проблема является выполнимой или невыполнимой в соответствии с этим решателем. Все остальные решатели прекращают работу. Диверсификация портфелей путем включения в них множества решателей, каждый из которых хорошо справляется с разным набором задач, повышает надежность решателя. [14]

    Многие решатели внутренне используют генератор случайных чисел . Диверсификация их семян — простой способ диверсифицировать портфель. Другие стратегии диверсификации включают включение, отключение или диверсификацию определенных эвристик в последовательном решателе. [15]

    Одним из недостатков параллельных портфелей является количество дублирующей работы. Если в последовательных решателях используется обучение предложений, совместное использование изученных предложений между параллельно работающими решателями может уменьшить дублирование работы и повысить производительность. Тем не менее, даже простое параллельное использование портфеля лучших решателей делает параллельный решатель конкурентоспособным. Примером такого решателя является PPfolio. [16] [17] Он был разработан для определения нижней границы производительности, которую должен обеспечить параллельный решатель SAT. Несмотря на большой объем дублирующей работы из-за отсутствия оптимизации, он хорошо работал на машине с общей памятью. ОрдаСат [18] — это параллельный решатель портфеля для больших кластеров вычислительных узлов. В своей основе он использует по-разному настроенные экземпляры одного и того же последовательного решателя. В частности, для жестких экземпляров SAT HordeSat может обеспечить линейное ускорение и, следовательно, значительно сократить время работы.

    В последние годы решатели SAT с параллельным портфолио доминировали на параллельной трассе Международных соревнований по решателям SAT. Яркими примерами таких решателей являются Plingeling и Painless-mcomsps. [19]

    Разделяй и властвуй

    [ редактировать ]

    В отличие от параллельных портфелей, принцип «разделяй и властвуй» пытается разделить пространство поиска между элементами обработки. Алгоритмы «разделяй и властвуй», такие как последовательный DPLL, уже применяют технику разделения пространства поиска, поэтому их расширение в сторону параллельного алгоритма является простым. Однако из-за таких методов, как распространение единиц после разделения, частичные проблемы могут значительно отличаться по сложности. Таким образом, алгоритм DPLL обычно не обрабатывает каждую часть пространства поиска за одинаковое время, что приводит к сложной проблеме балансировки нагрузки . [14]

    Дерево, иллюстрирующее этап прогнозирования и полученные кубы.
    Фаза куба для формулы . Эвристика принятия решений выбирает, какие переменные (кружки) назначить. После того, как эвристика отсечения решает остановить дальнейшее ветвление, частичные проблемы (прямоугольники) решаются независимо с помощью CDCL.

    Из-за нехронологического возврата назад распараллеливание изучения предложений, вызванного конфликтом, становится более трудным. Один из способов преодолеть это — парадигма «Кубируй и властвуй» . [20] Предлагается решить проблему в два этапа. На этапе «куба» Проблема разбивается на многие тысячи, вплоть до миллионов разделов. Это делается с помощью упреждающего решателя, который находит набор частичных конфигураций, называемых «кубами». Куб также можно рассматривать как объединение подмножества переменных исходной формулы. В сочетании с формулой каждый из кубиков образует новую формулу. Эти формулы могут решаться независимо и одновременно с помощью решателей, управляемых конфликтами. Поскольку дизъюнкция этих формул эквивалентна исходной формуле, задача считается выполнимой, если выполнима одна из формул. Упреждающий решатель подходит для решения небольших, но сложных задач. [21] поэтому он используется для постепенного разделения проблемы на несколько подзадач. Эти подзадачи проще, но все равно велики, что является идеальной формой для решения, управляемого конфликтами. Более того, решатели с упреждением рассматривают всю проблему, тогда как решатели, управляемые конфликтами, принимают решения на основе информации, которая гораздо более локальна. На этапе куба задействованы три эвристики. Переменные в кубах выбираются эвристикой принятия решений. Эвристика направления решает, какое присвоение переменной (истина или ложь) исследовать в первую очередь. В случаях, когда проблема решается, полезно сначала выбрать выполнимую ветвь. Эвристика отсечения решает, когда прекратить расширение куба и вместо этого направить его последовательному решателю, управляемому конфликтами. Предпочтительно, чтобы кубики были одинаково сложными для решения. [20]

    Treengeling — это пример параллельного решателя, применяющего парадигму Cube-and-Conquer. С момента своего появления в 2012 году он неоднократно добивался успехов на Международном конкурсе решателей SAT. Cube-and-Conquer использовался для решения булевой задачи пифагорейских троек . [22]

    Cube-and-Conquer — это модификация или обобщение основанного на DPLL подхода «разделяй и властвуй», который использовался для вычисления чисел Ван дер Вардена w(2;3,17) и w(2;3,18) в 2010 году. [23] где обе фазы (разделение и решение частичных задач) выполнялись с использованием DPLL.

    [ редактировать ]

    Одна из стратегий параллельного алгоритма локального поиска для решения SAT заключается в одновременной попытке нескольких переворотов переменных на разных процессорах. [24] Другой вариант — применить вышеупомянутый портфельный подход, однако совместное использование предложений невозможно, поскольку решатели локального поиска не создают предложения. В качестве альтернативы можно поделиться конфигурациями, созданными локально. Эти конфигурации можно использовать для создания новой начальной конфигурации, когда локальный решатель решает перезапустить поиск. [25]

    Рандомизированные подходы

    [ редактировать ]

    Алгоритмы, не входящие в семейство DPLL, включают стохастического локального поиска алгоритмы . Одним из примеров является WalkSAT . Стохастические методы пытаются найти удовлетворительную интерпретацию, но не могут сделать вывод, что экземпляр SAT невыполним, в отличие от полных алгоритмов, таких как DPLL. [4]

    Напротив, рандомизированные алгоритмы, такие как алгоритм PPSZ Патури, Пудлака, Сакса и Зейна, устанавливают переменные в случайном порядке в соответствии с некоторыми эвристиками, например, разрешением ограниченной ширины . Если эвристика не может найти правильную настройку, переменная назначается случайным образом. Алгоритм PPSZ имеет среду выполнения [ объяснить ] из для 3-САТ. Это была самая известная среда выполнения этой задачи до 2019 года, когда Хансен, Каплан, Замир и Цвик опубликовали модификацию этого алгоритма со временем выполнения для 3-САТ. Последний в настоящее время является самым быстрым известным алгоритмом k-SAT при всех значениях k. В ситуации со многими удовлетворительными заданиями рандомизированный алгоритм Шенинга имеет лучшую оценку. [26] [27] [28]

    Приложения

    [ редактировать ]

    По математике

    [ редактировать ]

    Решатели SAT использовались для доказательства математических теорем посредством компьютерного доказательства . В теории Рамсея несколько ранее неизвестных чисел Ван дер Вардена были вычислены с помощью специализированных решателей SAT, работающих на FPGA . [29] [30] В 2016 году Марин Хойле , Оливер Куллманн и Виктор Марек решили задачу булевых троек Пифагора с помощью решателя SAT, чтобы показать, что невозможно раскрасить целые числа до 7825 требуемым образом. [31] [32] Небольшие значения чисел Шура также были вычислены Хойле с использованием решателей SAT. [33]

    При проверке программного обеспечения

    [ редактировать ]

    Решатели SAT используются при формальной проверке аппаратного обеспечения и программного . При проверке модели (в частности, проверке ограниченной модели) решатели SAT используются для проверки того, удовлетворяет ли система с конечным числом состояний спецификации своего предполагаемого поведения. [34] [35]

    Решатели SAT являются основным компонентом, на котором теории модуля выполнимости построены решатели (SMT), которые используются для таких задач, как планирование заданий , символьное выполнение программы , проверка модели , проверка программы на основе логики Хоара и других приложений. [36] Эти методы также тесно связаны с программированием в ограничениях и логическим программированием .

    В других областях

    [ редактировать ]

    В исследовании операций решатели SAT применяются для решения задач оптимизации и планирования. [37]

    В теории социального выбора решатели SAT использовались для доказательства теорем невозможности. [38] Тан и Линь использовали решатели SAT, чтобы доказать теорему Эрроу и другие классические теоремы о невозможности. Гейст и Эндрисс использовали его, чтобы найти новые невозможности, связанные с расширениями множеств. Брандт и Гейст использовали этот подход, чтобы доказать невозможность создания стратегически устойчивых турнирных решений . Другие авторы использовали эту технологию, чтобы доказать новые невозможности, связанные с парадоксом неявки , половинной монотонностью и вероятностными правилами голосования . Брандл, Брандт, Петерс и Стрикер использовали его, чтобы доказать невозможность стратегического, эффективного и справедливого правила дробного социального выбора . [39]

    См. также

    [ редактировать ]

    Ссылки

    [ редактировать ]
    1. ^ Охрименко, Ольга; Стаки, Питер Дж.; Кодиш, Майкл (2007), «Распространение = ленивая генерация предложений», Принципы и практика программирования с ограничениями - CP 2007 , Конспекты лекций по информатике, том. 4741, стр. 544–558, CiteSeerX   10.1.1.70.5471 , doi : 10.1007/978-3-540-74970-7_39 , ISBN  978-3-540-74969-1 . современные решатели SAT часто могут решать задачи с миллионами ограничений и сотнями тысяч переменных
    2. ^ Дэвис, М.; Патнэм, Х. (1960). «Вычислительная процедура для количественной теории». Журнал АКМ . 7 (3): 201. дои : 10.1145/321033.321034 . S2CID   31888376 .
    3. ^ Дэвис, М .; Логеманн, Г.; Лавленд, Д. (1962). «Машинная программа для доказательства теорем» (PDF) . Коммуникации АКМ . 5 (7): 394–397. дои : 10.1145/368273.368557 . hdl : 2027/mdp.39015095248095 . S2CID   15866917 .
    4. ^ Jump up to: а б с Чжан, Линтао; Малик, Шарад (2002), «В поисках эффективных решателей логической выполнимости», Компьютерная проверка , Конспекты лекций по информатике, том. 2404, Springer Berlin Heidelberg, стр. 17–36, doi : 10.1007/3-540-45657-0_2 , ISBN  978-3-540-43997-4
    5. ^ Визель, Ю.; Вайсенбахер, Г.; Малик, С. (2015). «Решатели логической выполнимости и их применение при проверке моделей». Труды IEEE . 103 (11): 2021–2035. дои : 10.1109/JPROC.2015.2455034 . S2CID   10190144 .
    6. ^ Мёле, Сибилла; Бьер, Армин (2019). «Обратный возврат». Теория и применение тестирования выполнимости – SAT 2019 (PDF) . Конспекты лекций по информатике. Том. 11628. стр. 250–266. дои : 10.1007/978-3-030-24258-9_18 . ISBN  978-3-030-24257-2 . S2CID   195755607 .
    7. ^ Москевич, М.В.; Мэдиган, Калифорния; Чжао, Ю.; Чжан, Л.; Малик, С. (2001). «Chaff: Разработка эффективного решателя SAT» (PDF) . Материалы 38-й конференции по автоматизации проектирования (DAC) . п. 530. дои : 10.1145/378239.379017 . ISBN  1581132972 . S2CID   9292941 .
    8. ^ Маркес-Сильва, JP; Сакалла, штат Калифорния (1999). «GRASP: алгоритм поиска пропозициональной выполнимости» (PDF) . Транзакции IEEE на компьютерах . 48 (5): 506. дои : 10.1109/12.769433 . Архивировано из оригинала (PDF) 4 ноября 2016 г. Проверено 28 августа 2015 г.
    9. ^ http://www.cril.univ-artois.fr/~jabbour/manysat.htm [ только URL ]
    10. ^ «Веб-страница международных соревнований SAT» . Проверено 15 ноября 2007 г.
    11. ^ «Конкурс САТ 2016» . baldur.iti.kit.edu . Проверено 13 февраля 2020 г.
    12. ^ «Конкурс САТ 2017» . baldur.iti.kit.edu . Проверено 13 февраля 2020 г.
    13. ^ «Конкурс САТ 2018» . sat2018.forsyte.tuwien.ac.at . Проверено 13 февраля 2020 г.
    14. ^ Jump up to: а б Бальо, Томаш; Синц, Карстен (2018), «Параллельная выполнимость», Справочник по рассуждению о параллельных ограничениях , Springer International Publishing, стр. 3–29, doi : 10.1007/978-3-319-63516-3_1 , ISBN  978-3-319-63515-6
    15. ^ Бьер, Армин. «Lingeling, Plingeling, PicoSAT и PrecoSAT на SAT Race 2010» (PDF) . САТ-ГОНКА 2010 .
    16. ^ «Решатель ppfolio» . www.cril.univ-artois.fr . Проверено 29 декабря 2019 г.
    17. ^ «Конкурс SAT 2011: Трек 32 ядра: рейтинг решателей» . www.cril.univ-artois.fr . Проверено 13 февраля 2020 г.
    18. ^ Бальо, Томаш; Сандерс, Питер; Синц, Карстен (2015), «HordeSat: решатель SAT с массовым параллельным портфелем», Теория и применение тестирования выполнимости - SAT 2015 , Конспекты лекций по информатике, том. 9340, Springer International Publishing, стр. 156–172, arXiv : 1505.03340 , doi : 10.1007/978-3-319-24318-4_12 , ISBN  978-3-319-24317-7 , S2CID   11507540
    19. ^ «Конкурс САТ 2018» . sat2018.forsyte.tuwien.ac.at . Проверено 13 февраля 2020 г.
    20. ^ Jump up to: а б Хойле, Марин Дж. Х .; Куллманн, Оливер; Виринга, Сиерт; Бьер, Армин (2012), «Cube and Conquer: руководство по решателям CDCL SAT с помощью Lookaheads», Аппаратное и программное обеспечение: проверка и тестирование , конспекты лекций по информатике, том. 7261, Springer Berlin Heidelberg, стр. 50–65, doi : 10.1007/978-3-642-34188-5_8 , ISBN  978-3-642-34187-8
    21. ^ Хойле, Марин Дж. Х .; ван Маарен, Ганс (2009). «Решатели SAT на основе прогноза» (PDF) . Справочник по выполнимости . ИОС Пресс. стр. 155–184. ISBN  978-1-58603-929-5 .
    22. ^ Хойле, Марин Дж. Х .; Куллманн, Оливер; Марек, Виктор В. (2016), «Решение и проверка булевой задачи троек Пифагора с помощью алгоритма Cube and Conquer», Теория и применение проверки выполнимости – SAT 2016 , Конспекты лекций по информатике, том. 9710, Springer International Publishing, стр. 228–245, arXiv : 1605.00723 , doi : 10.1007/978-3-319-40970-2_15 , ISBN  978-3-319-40969-6 , S2CID   7912943
    23. ^ Ахмед, Танбир (2010). «Два новых числа Ван дер Вардена w(2;3,17) и w(2;3,18)». Целые числа . 10 (4): 369–377. дои : 10.1515/integ.2010.032 . МР   2684128 . S2CID   124272560 .
    24. ^ Роли, Андреа (2002), «Критичность и параллелизм в структурированных экземплярах SAT», Принципы и практика программирования с ограничениями - CP 2002 , Конспекты лекций по информатике, том. 2470, Springer Berlin Heidelberg, стр. 714–719, doi : 10.1007/3-540-46135-3_51 , ISBN  978-3-540-44120-5
    25. ^ Арбелаес, Алехандро; Хамади, Юсеф (2011), «Улучшение параллельного локального поиска для SAT», Обучение и интеллектуальная оптимизация , Конспекты лекций по информатике, том. 6683, Springer Berlin Heidelberg, стр. 46–60, doi : 10.1007/978-3-642-25566-3_4 , ISBN  978-3-642-25565-6 , S2CID   14735849
    26. ^ Шенинг, Уве (октябрь 1999 г.). «Вероятностный алгоритм для решения задач k-SAT и удовлетворения ограничений» (PDF) . 40-й ежегодный симпозиум по основам информатики (кат. № 99CB37039) . стр. 410–414. дои : 10.1109/SFCS.1999.814612 . ISBN  0-7695-0409-4 . S2CID   123177576 .
    27. ^ «Улучшенный алгоритм экспоненциального времени для k-SAT» , Патури, Пудлак, Сакс, Зани
    28. ^ «Быстрые алгоритмы k-SAT с использованием смещенного PPSZ» , Хансен, Каплан, Замир, Цвик
    29. ^ Курил, Михал; Пол, Джером Л. (2008). «Число Ван дер Вардена $W(2,6)$ равно 1132» . Экспериментальная математика . 17 (1): 53–61. дои : 10.1080/10586458.2008.10129025 . ISSN   1058-6458 . S2CID   1696473 .
    30. ^ Курил, Михал (2012). «Вычисление числа Ван дер Вардена W (3,4) = 293». Целые числа . 12 : А46. МР   3083419 .
    31. ^ Хойле, Марин Дж. Х.; Куллманн, Оливер; Марек, Виктор В. (2016), «Решение и проверка булевой задачи троек Пифагора с помощью алгоритма Cube and Conquer», Теория и применение проверки выполнимости – SAT 2016 , Конспекты лекций по информатике, том. 9710, стр. 228–245, arXiv : 1605.00723 , doi : 10.1007/978-3-319-40970-2_15 , ISBN  978-3-319-40969-6 , S2CID   7912943
    32. ^ Лэмб, Эвелин (01 июня 2016 г.). «Доказательство по математике объемом в двести терабайт — самое большое за всю историю» . Природа . 534 (7605): 17–18. Бибкод : 2016Natur.534...17L . дои : 10.1038/nature.2016.19990 . ISSN   1476-4687 . ПМИД   27251254 . S2CID   5528978 .
    33. ^ «Шур номер пять» . www.cs.utexas.edu . Проверено 26 октября 2023 г.
    34. ^ Кларк, Эдмунд; Бьер, Армин; Рэйми, Ричард; Чжу, Юньшань (1 июля 2001 г.). «Проверка ограниченной модели с использованием решения выполнимости» . Формальные методы проектирования систем . 19 (1): 7–34. дои : 10.1023/А:1011276507260 . ISSN   1572-8102 . S2CID   2484208 .
    35. ^ Бьер, Армин; Чиматти, Алессандро; Кларк, Эдмунд М.; Стрихман, Офер; Чжу, Юньшань (2003). «Проверка ограниченной модели» (PDF) . Достижения в области компьютеров . 58 (2003): 117–148. дои : 10.1016/S0065-2458(03)58003-2 . ISBN  9780120121588 – через академическую прессу.
    36. ^ Де Моура, Леонардо; Бьорнер, Николай (01 сентября 2011 г.). «Теории выполнимости по модулю: введение и приложения» . Коммуникации АКМ . 54 (9): 69–77. дои : 10.1145/1995376.1995394 . ISSN   0001-0782 . S2CID   11621980 .
    37. ^ Коэльо, Хосе; Ванхук, Марио (16 августа 2011 г.). «Многорежимное планирование проектов с ограниченными ресурсами с использованием решателей RCPSP и SAT» . Европейский журнал операционных исследований . 213 (1): 73–82. дои : 10.1016/j.ejor.2011.03.019 . ISSN   0377-2217 .
    38. ^ Петерс, Доминик (2021). «Пропорциональность и стратегическая устойчивость на выборах с несколькими победителями». arXiv : 2104.08594 [ cs.GT ].
    39. ^ Брандл, Флориан; Брандт, Феликс; Петерс, Доминик; Стрикер, Кристиан (18 июля 2021 г.). «Правила распределения при дихотомических предпочтениях: два из трех — неплохо» . Материалы 22-й конференции ACM по экономике и вычислениям . ЭК '21. Нью-Йорк, штат Нью-Йорк, США: Ассоциация вычислительной техники. стр. 158–179. дои : 10.1145/3465456.3467653 . ISBN  978-1-4503-8554-1 . S2CID   232109303 .
    [ редактировать ]
    • Обзор субботних соревнований с 2002 года.
    Retrieved from "https://en.wikipedia.org/w/index.php?title=SAT_solver&oldid=1191275898#Parallel_SAT-solving"
    Arc.Ask3.Ru: конец переведенного документа.
    Arc.Ask3.Ru
    Номер скриншота №: 693befbe5ea4fd6b05562063e8ea99c7__1703247960
    URL1:https://arc.ask3.ru/arc/aa/69/c7/693befbe5ea4fd6b05562063e8ea99c7.html
    Заголовок, (Title) документа по адресу, URL1:
    SAT solver - Wikipedia
    Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)