Страница 4 последний абзац, там вводится понятие побочных (superfluous) подструктур. Это как раз 0111 и 1110. В оставшейся части статьи как раз и идет борьба с такими подструктурами, в частности процедурой фильтрации. Процедура фильтрации определяется как часть операции продвижения (shift). Она гарантирует, что каждая вершина не будет состоять только из побочных структур.
То есть из того, что в каждой вершине есть непустая структура, не следует, что там существует решение.
Не следует. Но если последний уровень системы гиперструктур построен не пустым, то значит в каждой вершине последнего уровня есть решение по построению. Как его найти — другой вопрос.
satcompetition — это соревнования для алгоритмов, основанных на эвристиках. Они очень быстрые в большинстве случаев. Алгоритм Романова — это алгоритм общего назначения. Он работает всегда одинаково (O(n^4*m)) для всех случаев.
По вопросам.
1. Вы правильно поняли про CTF — это формулы с определенным порядком дизъюнктов. В дальнейшем же алгоритме участвуют их дополнения. Причем дополнения строятся так, что количество переменных в них все-равно равно n. Даже если в какой то CTF была одна тройка, то ее дополнение будет содержать n-2 уровня на каждом из которых по 8 троек, кроме одного уровня — на нем будет 7 троек.
2. В этом случае вершина продвигается (shift) по обоим ребрам. Причем она должна быть продвинута непусто во всех гиперструктурах. Если хотя бы в одной гиперструктуре она продвигается пустой, то считается, что во всех гиперструктурах она продвинулась пустой.
Мы использовали некоторые задачи оттуда в своих тестах.
Я уже писал выше о размерности задач и невозможности решать большие экземпляры на персоналках.
Еще мы решали задачи отсюда: www.cs.ubc.ca/~hoos/SATLIB/benchm.html
На этой реализации масштабный эксперимент мы не ставили, решили несколько тысяч задач с числом переменных n=20, 50, 75, 100, 125, 400
Первые решаются за несколько секунд, для задачи в 400 переменных ушло 14 часов. Сейчас может быть уже 7, я пока не пробовал, вчера только закомитил хорошую оптимизацию.
Если у кого-то есть свободные вычислительные ресурсы, чтобы запустить решение — напишите здесь.
Следует написать, наверное, что я все это делаю в свободное от работы время, поэтому времени немного не хватает :)
Если честно, я не понял откуда получилось n^128 :)
Если сведение имеет какую то сложность, пусть 2^5, то эта сложность аддитивная. В результате мы все-равно получаем задачу 3-ВЫП. Только вот количество переменных, то есть n, может сильно вырасти.
При сложности n^4 и значении n=1000 — это уже не мало. В реальных задачах (в частности ниже есть ссылка на sat competition) для 3-SAT самый большой пример имеет n = 18000. Это много :)
На тех же соревнованиях есть примеры с количеством переменных n = 4 000 000 и это k-SAT. При сведении к 3-SAT количество переменных может увеличиться в разы.
Кроме этого не нужно забывать, что у задачи есть еще один параметр — это количество скобок — m. Она тоже фигурирует в формуле сложности. И часто m > n. То есть в формуле n^4 можно смело прибавлять 1 в общем случае.
Это все-равно долго, но: 1) статья имеет теоретическую значимость 2) это алгоритм, на котором построено доказательство. У меня есть несколько идей, как его улучшить и снизить степень полинома.
Еще при первом прочтении никто не обращает внимание на ресурсы памяти. Задача на n=1000 в текущей реализации требует 13ГБ ОЗУ. Это можно поправить, оптимизировав структуры данных. По моим подсчетам это позволит сократить объем памяти в 40 раз. Но все-равно для больших задач одной «персоналки» будет не достаточно. Нужно строить вычислительный кластер/сеть.
Похожая программа есть в дистрибутивах Delphi в папке «c:\Program Files\Borland\Delphi7\Demos\Threads» (я заметил только в версии 7 в первый раз, но думаю с версии 3 он уже там).
Там такими же квадратиками с полосками иллюстрируется многопоточность на примере трех алгоритмов сортировки: пузырьковая, выбором и быстрая.
Всегда показываю этот пример студентам на лекциях… каждый раз у аудитории безумный восторг от этих полосочек.
А еще строит гистограмму распределения времени ответа, которая тоже очень полезна, чтобы узнать режимы работы.
Он бесплатный (потому что пока что укладывается в бесплатную квоту). Он в облаке Google Appengine (не РФ).
Единственное серьезное ограничение, которое накладывает AppEngine — невозможность получить логи ping/tracert (и вообще пользоваться системными утилитами). Из-за этого нельзя сделать действительно серьезный анализ работы сайта, за который можно заплатить.
У вас такой диагностики тоже нет. Так, все-таки, чем вы лучше других?
Хотя, конечно, я не исключаю, что в «официальном отчете по доступности ресурсов» есть что-то полезное. Можно пример такого отчета посмотреть?
Я сегодня встречался с Владимиром Федоровичем, он был немного занят, договорились встретиться и поговорить предметно в следующий понедельник. Обязательно напишу результаты в оригинальной ветке.
По разговору с Романовым я выяснил, что есть приложение (написанное на Delphi), в котором реализован алгоритм. Но он был сделан на скорую руку. Возможно прийдется его немного порефакторить. В следующий понедельник я постараюсь взять это приложение и опубликовать исходники. Когда выложу — напишу здесь.
Есть статья на английском (я обновил пост). Я не в курсе, куда отправил Деолаликар экземпляр. Можете дать email'ы, или другой способ, кому можно отправить?
Насколько я знаю, эта чехарда с рецензентами идет раньше чем с 2007 года и все недочеты с форматированием (лишние запятые, кавычки и прочее) уже давно исправлены. Просто работу никак не хотят признавать.
Не знаю почему нет отзывов от российских коллег-математиков… может быть они и есть? Уточню, напишу позже.
Реализация алгоритма не держится в секрете. Я не занимался реализацией, поэтому не могу сказать достаточно ли материала статьи, чтобы его запрограммировать, но, думаю, достаточно. Кстати, если я правильно помню, реализация появилась как раз в результате общения с рецензентами, чтобы подтвердить полиномиальность и безошибочность алгоритма. Поэтому в статье и появился пункт 7 «Апробация алгоритма и выводы». Не думаю что исходники реализации могут сыграть какую-то важную роль, хотя для независимой оценки может быть будут полезны. Я попробую их достать и выложить где-нибудь здесь.
Никакого сговора, конечно, нет. Я могу предположить что проблема в том, что из нашего окружения никто подобные материалы никогда не публиковал и не знает что и как нужно делать.
Я уверен на 100%, что если бы Владимиру Федоровичу было 30-40 лет он бы нашел способ как добиться публикации. Видимо когда вам за 60 все становится не так просто.
P.S.
Насчет arxiv.org — обязательно передам, тем более, что английский вариант уже должен быть.
Архитектуру придумали до того как я попал на проект, не могу сказать какая была задумка. Но могу сказать, что быстрее точно не работает.
Зато есть один неприятный момент: из-за того что работа может вестись одновременно с двумя соединениями, то может начаться распределенная транзакция и если на сервере она не сконфигурирована (а на наших dev-серверах она не настроена), получаем exception. Основное неудобство — с тестами. Обычно, если тесту нужна база, просто оборачиваем тело метода в TransactionScope и в конце делаем rollback. А с двумя базами так не получается.
Не следует. Но если последний уровень системы гиперструктур построен не пустым, то значит в каждой вершине последнего уровня есть решение по построению. Как его найти — другой вопрос.
По вопросам.
1. Вы правильно поняли про CTF — это формулы с определенным порядком дизъюнктов. В дальнейшем же алгоритме участвуют их дополнения. Причем дополнения строятся так, что количество переменных в них все-равно равно n. Даже если в какой то CTF была одна тройка, то ее дополнение будет содержать n-2 уровня на каждом из которых по 8 троек, кроме одного уровня — на нем будет 7 троек.
2. В этом случае вершина продвигается (shift) по обоим ребрам. Причем она должна быть продвинута непусто во всех гиперструктурах. Если хотя бы в одной гиперструктуре она продвигается пустой, то считается, что во всех гиперструктурах она продвинулась пустой.
Я уже писал выше о размерности задач и невозможности решать большие экземпляры на персоналках.
Еще мы решали задачи отсюда: www.cs.ubc.ca/~hoos/SATLIB/benchm.html
На этой реализации масштабный эксперимент мы не ставили, решили несколько тысяч задач с числом переменных n=20, 50, 75, 100, 125, 400
Первые решаются за несколько секунд, для задачи в 400 переменных ушло 14 часов. Сейчас может быть уже 7, я пока не пробовал, вчера только закомитил хорошую оптимизацию.
Если у кого-то есть свободные вычислительные ресурсы, чтобы запустить решение — напишите здесь.
Следует написать, наверное, что я все это делаю в свободное от работы время, поэтому времени немного не хватает :)
Если сведение имеет какую то сложность, пусть 2^5, то эта сложность аддитивная. В результате мы все-равно получаем задачу 3-ВЫП. Только вот количество переменных, то есть n, может сильно вырасти.
При сложности n^4 и значении n=1000 — это уже не мало. В реальных задачах (в частности ниже есть ссылка на sat competition) для 3-SAT самый большой пример имеет n = 18000. Это много :)
На тех же соревнованиях есть примеры с количеством переменных n = 4 000 000 и это k-SAT. При сведении к 3-SAT количество переменных может увеличиться в разы.
Кроме этого не нужно забывать, что у задачи есть еще один параметр — это количество скобок — m. Она тоже фигурирует в формуле сложности. И часто m > n. То есть в формуле n^4 можно смело прибавлять 1 в общем случае.
Это все-равно долго, но: 1) статья имеет теоретическую значимость 2) это алгоритм, на котором построено доказательство. У меня есть несколько идей, как его улучшить и снизить степень полинома.
Еще при первом прочтении никто не обращает внимание на ресурсы памяти. Задача на n=1000 в текущей реализации требует 13ГБ ОЗУ. Это можно поправить, оптимизировав структуры данных. По моим подсчетам это позволит сократить объем памяти в 40 раз. Но все-равно для больших задач одной «персоналки» будет не достаточно. Нужно строить вычислительный кластер/сеть.
Там такими же квадратиками с полосками иллюстрируется многопоточность на примере трех алгоритмов сортировки: пузырьковая, выбором и быстрая.
Всегда показываю этот пример студентам на лекциях… каждый раз у аудитории безумный восторг от этих полосочек.
Сравнение скорости и описание алгоритмов (с кодом на Pascal) есть у Вирта: www.mat.net.ua/mat/Virt-Algoritmi-programmi.htm
Не только.
Даже Ping Service показывает время ответа.
А еще строит гистограмму распределения времени ответа, которая тоже очень полезна, чтобы узнать режимы работы.
Он бесплатный (потому что пока что укладывается в бесплатную квоту). Он в облаке Google Appengine (не РФ).
Единственное серьезное ограничение, которое накладывает AppEngine — невозможность получить логи ping/tracert (и вообще пользоваться системными утилитами). Из-за этого нельзя сделать действительно серьезный анализ работы сайта, за который можно заплатить.
У вас такой диагностики тоже нет. Так, все-таки, чем вы лучше других?
Хотя, конечно, я не исключаю, что в «официальном отчете по доступности ресурсов» есть что-то полезное. Можно пример такого отчета посмотреть?
У вас есть опыт публикации статьи на arxiv.org? С первого просмотра я не смог там найти формы отправки публикации. Можете посодействовать?
Не знаю почему нет отзывов от российских коллег-математиков… может быть они и есть? Уточню, напишу позже.
Реализация алгоритма не держится в секрете. Я не занимался реализацией, поэтому не могу сказать достаточно ли материала статьи, чтобы его запрограммировать, но, думаю, достаточно. Кстати, если я правильно помню, реализация появилась как раз в результате общения с рецензентами, чтобы подтвердить полиномиальность и безошибочность алгоритма. Поэтому в статье и появился пункт 7 «Апробация алгоритма и выводы». Не думаю что исходники реализации могут сыграть какую-то важную роль, хотя для независимой оценки может быть будут полезны. Я попробую их достать и выложить где-нибудь здесь.
Никакого сговора, конечно, нет. Я могу предположить что проблема в том, что из нашего окружения никто подобные материалы никогда не публиковал и не знает что и как нужно делать.
Я уверен на 100%, что если бы Владимиру Федоровичу было 30-40 лет он бы нашел способ как добиться публикации. Видимо когда вам за 60 все становится не так просто.
P.S.
Насчет arxiv.org — обязательно передам, тем более, что английский вариант уже должен быть.
Зато есть один неприятный момент: из-за того что работа может вестись одновременно с двумя соединениями, то может начаться распределенная транзакция и если на сервере она не сконфигурирована (а на наших dev-серверах она не настроена), получаем exception. Основное неудобство — с тестами. Обычно, если тесту нужна база, просто оборачиваем тело метода в TransactionScope и в конце делаем rollback. А с двумя базами так не получается.