?

Log in

No account? Create an account
P ≠ NP - Олег Етеревский [entries|archive|friends|userinfo]
Oleg Eterevsky

[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

P ≠ NP [23 January 2011|03:20]
Oleg Eterevsky
[Tags|, ]

Опять для математиков

Продолжаю из чистого интереса разбираться с хабровским алгоритмом для 3-SAT. Решил действовать эвристически. Написал програмку, генерирующую формулу для разложения на множители. Солвер успешно разложил число 121. Заняло это полчаса (207 переменных, 839 скобок). Не менее успешно доказал простоту числа 127. Сейчас запущу на числе 239.

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

P.S. Кстати, я раньше не задумывался, насколько легко, оказывается, сводится факторизация к 3-SAT. Всего 250 строчек на питоне. Написал часа за 2 наверное. Вот, если кому интересно.

LinkReply

Comments:
[User Picture]From: edwardahirsch
2011-01-23 07:01 am (UTC)
Скормите ему формулы с моей веб-страницы.
(Reply) (Thread)
[User Picture]From: eterevsky
2011-01-23 09:37 am (UTC)
О! Спасибо. Мои формулы cryptominisat решал мгновенно, на Вашей подзадумался. :-)
(Reply) (Parent) (Thread)
[User Picture]From: dmitrygusev
2011-01-23 09:19 am (UTC)
Могу порекомендовать использовать ключик -a, тогда солвер будет работать быстрее.
(Reply) (Thread)
[User Picture]From: eterevsky
2011-01-23 09:38 am (UTC)
Спасибо.
(Reply) (Parent) (Thread)
[User Picture]From: dcab
2011-01-23 05:58 pm (UTC)

Как пользоваться скриптом?

Те как запускать понятно, а как ему указывать какие числа раскладывать?

И можно сылочку где описан сам алгоритм по которому вы писали скрипт.
(Reply) (Thread)
[User Picture]From: eterevsky
2011-01-23 06:43 pm (UTC)

Re: Как пользоваться скриптом?

Прошу прощения, я писал скрипт на коленке и не озаботился такими мелочами как культурный ввод-вывод. В строчке 240 в переменной n задаётся битность операций. В строчке 243 задаётся число, которое мы раскладываем на множители. Это число должно быть < 2^(n+1).

Писал я это из головы, идея проста. Представляем в первых 2n битах число, которое будем раскладывать. Пишем часть формулы, которая задаст для этих битов константное значение, то которое нам нужно. Следующие два блока по n битов -- предполагаемые сомножители, на которые число будет раскладываться. Пишем условия, что оба этих числа > 1 (с точки зрения битов это значит, что есть бит кроме младшего, отличный от 0). Дальше честно пишем умножение в столбик -- представляем x = y * z в виде большого набора логических условий на битах.

Получили формулу. Если она unsatisfiable, то число на множители не раскладывается. Если мы знаем набор значений, на которых она выполняется, то если мы посмотрим на последовательности битов, которыми мы обозначили сомножители, то узнаем разложение.
(Reply) (Parent) (Thread)
[User Picture]From: mihaild
2011-01-23 07:37 pm (UTC)
Спасибо, интересный результат.
Насколько я понимаю, число переменных растет линейно, а число скобок - примерно квадратично по битности числа? Тогда при заявленной сложности (количество переменных)^4*(количество скобок) у нас получается шестая степень по размеру числа. В целом неплохо)

Это, конечно, какая-то эвристика. Работает она, судя по всему, довольн неплохо.
Кстати, насколько я понимаю, ложно-отрицательных срабатываний алгоритм давать не должен. Если авторы на своих тестах проверяли корректность положительных - то, похоже, подобрать контрпример будет не очень просто.
(Reply) (Thread)
[User Picture]From: eterevsky
2011-01-23 08:17 pm (UTC)
Я, кстати, запустил программу на положительном примере вот отсюда. Пождал 5 с лишним часов и прибил. На ночь опять запущу. Хотя задача там небольшая, 200 с чем-то переменных на 400 условий.
(Reply) (Parent) (Thread)
[User Picture]From: dmitrygusev
2011-01-24 08:01 am (UTC)
Это точно 3-SAT? Может там k-SAT?
Я тоже запустил вчера задачу hgen8-n260-01-S1597732451.shuffled-as.sat03-885.cnf. Это k-SAT, она свелась к 3-SAT на 603 переменных и 782 скобки. Там система гиперструктур уже построена, сейчас идет поиск выполняющего набора (работает уже 22 часа и занимает 4,7 ГБ RAM).
(Reply) (Parent) (Thread)
[User Picture]From: eterevsky
2011-01-24 09:43 am (UTC)
А, да, действительно, это SAT, а не 3-SAT. Там 80% формул — с двумя переменными, а оставшиеся — с 4-я.
(Reply) (Parent) (Thread)
[User Picture]From: eterevsky
2011-01-24 12:18 pm (UTC)
Секунду. Так hgen8 — unsatisfiable. Если у Вас построились непустые гиперструктуры, значит, это — искомый контрпример.
(Reply) (Parent) (Thread)
[User Picture]From: dmitrygusev
2011-01-24 01:13 pm (UTC)
Да, я нашел еще одну невыполнимую формулу (x1_16.shuffled.cnf из SAT Competitions 2002), на которой строится непустая гиперструктура.
Буду разбираться, возможно это просто ошибка в реализации.
(Reply) (Parent) (Thread)
[User Picture]From: mihaild
2011-01-27 07:34 pm (UTC)
Как разберетесь - отпишетесь, хорошо?
(Reply) (Parent) (Thread)
[User Picture]From: dmitrygusev
2011-01-27 08:58 pm (UTC)
Отпишусь обязательно.

Я сделал issue на github, можете за ним следить тоже: https://github.com/anjlab/sat3/issues#issue/5

Еще я закомитил тест, на котором воспроизводится ошибка. Там всего 45 переменных и 2 СКТ (одна гиперструктура получается).

Скорее всего ошибка где-то в алгоритме фильтрафии, потому что она пропустила структуру, в которой только побочные пересечения, я сейчас в этом направлении разбираюсь.
(Reply) (Parent) (Thread)
[User Picture]From: dmitrygusev
2013-09-25 06:00 am (UTC)
Сегодня вышла новая публикация Романова -- развитие прежнего алгоритма. В новой версии гиперструктуры отсутствуют (и соответственно процедуры, которые вносили дефект в алгоритм), поэтому такой ошибки в ней быть не может.

Реализации этого алгоритма на данный момент не существует, поэтому проверить насколько хорошо он работает я не могу, но для ознакомления оставляю здесь ссылку на публикацию:

http://romvf.wordpress.com/2013/09/25/development-of-the-concept/
(Reply) (Parent) (Thread)