Сегодня в блоге Скотта Ааронсона приведен список интересных открытых задач / задач по сложности. Один из них привлек мое внимание:

Создайте публичную библиотеку из 3SAT-экземпляров, используя как можно меньше переменных и предложений, что может привести к значительным последствиям в случае ее решения. (Например, экземпляры, кодирующие задачи факторинга RSA.) Изучите производительность лучших текущих SAT-решателей в этой библиотеке.

Это вызвало у меня вопрос: какова стандартная методика сокращения проблем RSA / факторинга до SAT и насколько быстро это происходит? Есть ли такое стандартное сокращение?

Просто чтобы прояснить, под «быстрым» я не подразумеваю полиномиальное время. Мне интересно, есть ли у нас более жесткие верхние границы сложности сокращения. Например, есть ли известное кубическое сокращение?

Один из подходов для кодирования факторинга (RSA) в SAT заключается в использовании схем мультипликатора (каждая схема может быть закодирована как CNF).

Предположим, нам дано целое число с 2 n битами, C = ( c 1 , c 2 , ⋯ , c 2 n ) 2 . Нас интересует поиск двух n- битных целых чисел A = ( a 1 , ⋯ , a n ) и A = ( b 1 , ⋯ , b n ) , произведение которых C = A $C$$2n$$C=(c_1,c_2,\cdots,c_{2n})_2$$n$$A=(a_1,\cdots,a_n)$$A=(b_1,\cdots,b_n)$ .$C=A*B$

Самая наивная кодировка может быть примерно такой: мы знаем, что

с 2 п - 1 = ( п ∧ б п - 1 ) х ö г ( п - 1 ∧ б п ) С г г у : г 2 п - 1 = ( в n ∧ b n - 1 ) ∧ ( a

Затем с использованием преобразования Цейтин вышеуказанное кодирование может быть переведено в CNF.

Этот подход производит относительно маленький CNF. Но эта кодировка не поддерживает «Unit Propagation», поэтому производительность SAT Solvers действительно плохая.

Есть другие схемы для умножения, которые могут быть использованы для этой цели, но они производят больший CNF.

Продолжая то, что написал @Amir, я наткнулся на следующую симпатичную веб-страницу, на которой размещен генератор CNF для схем факторинга, которые можно, например, запускать на некоторых (теперь неактивных) номерах RSA Factoring Challenge . Сгенерированные экземпляры имеют формат DIMACS , который может напрямую передаваться любому из текущих конкурентов на ежегодном конкурсе SAT solver . Что касается сложных экземпляров SAT в целом, проблемы с эталонным тестом, представленные на сайте соревнований SAT, представляются весьма полезными, а также неплохо классифицировать их на случайные / специально созданные / промышленные.

Вот статья о создании экземпляров SAT из факторинга:

Хори, С. & Ватанабе, О. [1997] Алгоритмы и вычисления " Создание жесткого экземпляра для SAT " 1350: 22-31 ( pdf )

$n^2$

ToughSat от Henry Yuen и Joseph Bebel - еще один инструмент, похожий на тот, что связан с @Martin, который генерирует формулы CNF, которые кодируют случаи факторинга и другие сложные проблемы.

Смотрите satfactor:

Преобразовать целочисленную факторизацию в булеву проблему удовлетворенности

Шейн Неф

обзор

Определение факторов большого целого числа представляло интерес для человека, по крайней мере, со времен Евклида. Не существует известного общего алгоритма для этой задачи, который масштабируется менее чем за экспоненциальное время по отношению к числу битов, необходимых для представления целого числа.

Что делает этот код

Преобразует целочисленную проблему факторизации в булеву проблему СООТВЕТСТВИЯ. Если проблема решается с помощью решателя SAT, он извлекает целочисленные коэффициенты.

Решатели буленовской удовлетворенности улучшаются с каждым годом. Каждые 2 года проводится международный конкурс между решателями (см. Http://www.satcompetition.org/ и http://www.satlive.org/ ). Насколько хорошо эти современные решатели могут справиться с одной из самых старых существующих математических задач?

Этот проект преследует 2 основные цели:
1) Преобразовать задачу и вычислить целое число, представляющее интерес!
2) Быстро создать либо разрешимую, либо неразрешимую проблему СООТВЕТСТВИЯ, сложность которой легко контролируется создателем.
- Чтобы создать неразрешимую проблему удовлетворенности, просто закодируйте простое число.
- Чтобы создавать более сложные, но решаемые проблемы, выбирайте составные числа большего размера с меньшим количеством факторов.

Количество процентов может быть любого размера!

Есть некоторые решатели с открытым исходным кодом SATISFIABILITY. Смотрите http://www.satlive.org/ для некоторых из них.

Сложение

make -C src /

Как

Введите интересующий вас номер в двоичном виде:

bin / iencode 10101> смесь.21
// решаем с помощью вашего любимого решателя и помещаем результаты в solution.txt
bin / extract-sat смесь.21 solution.txt

Выход будет:
00011
00111

которые представляют собой двоичные представления для десятичных целых 3 и 7, множители 21.

Если входное целое число имеет более 2 факторов, и проблема SAT решена, выходные данные будут только двумя из факторов. Это могут быть не простые числа (вы можете легко проверить это в Maxima, Maple или Mathematica).

Не все SAT-решатели выводят результаты в одном и том же формате. Возможно, вам придется немного скорректировать эти результаты. extract-sat требует файл решения, содержащий список целых чисел (на любое количество строк). Например,

1 -2 3 4 -5 ...