Открыть список
Как стать автором
Обновить
14
Карма
0
Рейтинг
dmitrygusev @dmitrygusev

Пользователь

Зачем нам всем нужен SAT и все эти P-NP (часть вторая)

Все правильно, да. Статья про полиномиальный алгоритм для 3-SAT.
Если алгоритм правильный — это бы означало, что P == NP, но доказать равенство — не цель статьи.

Зачем нам всем нужен SAT и все эти P-NP (часть вторая)

Я чего-то не понимаю, но, мне кажется, эти утверждения противоречат друг другу?

В чем противоречие? Может быть я не так выразился?

Зачем нам всем нужен SAT и все эти P-NP (часть вторая)

т.е. банально никто на самом деле не проверял, а не было ли предложено похожих и/или эквивалентных методов?


Не могу отвечать за Романова. Я не проверял. Думаю он тоже, но это только мое мнение.

Всех интересует, чем же она действительно отличается, иначе смысл заниматься её изучением?


Ну вот вы же разобрались, чем один алгоритм отличается от другого и выше тут привели.
Или это не вы разбирались, а прочитали в статье других авторов?
Я не разбирался в чем отличие, потому что сначала надо разобраться в этом алгоритме, прежде чем его сравнивать.
А чтобы хорошо разобраться, лучше его реализовать и протестировать. Мной пока этого сделано не было.
От Владимира Федоровича я тоже не слышал этого.

Зачем нам всем нужен SAT и все эти P-NP (часть вторая)

Со стороны всегда просто рассуждать, почему одну работу ждет провал, а другую успех.

Конечно, на весь ваш список «здравого смысла» у меня (и, я уверен, у Владимира Федоровича) есть положительные ответы, но дело даже не в этом.

Статья не претендует на доказательства P ?= NP, в ней просто предлагается алгоритм решения 3-SAT и предлагается новый взгляд на представление этой задачи в виде структур компактных троек, который никто за 40 лет не предлагал, поэтому и нет ссылок — это новая работа, новый подход. И новая NP-полная задача. Искать сходства или различия с существующими подходами и алгоритмами — это не то, чем занимался автор.

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

Я могу понять, что у вас (и остальных) нет желания разбираться в новой статье, пока даже Романов не исследовал свой подход на практике и не опубликовал результаты. Не исследовал, в частности, потому что нет прототипа. Но его пока нет, и нет только потому, что его просто некому написать. Все действительно так просто.

Я также соглашусь, что в статье нет формального описания алгоритма. Его не было и в прошлой работе, прототип для которой был написан несколько раз. Один, последний, написал я в свое свободное время, постоянно консультируясь с Владимиром Федоровичем в течение 3-х месяцев. Видимо, с этой статьей нужно работать так же… кто возьмется пока я занят? Контакты обеспечу.

Если говорить о статье, в ней приводится именно конструктивное доказательство алгоритма и, кстати, solver от предыдущей работы ни разу не дал ложного решения с практической точки зрения — если формула выполнима он давал выполняемый набор, если нет — набора, соответственно, не выдавалось. И все это за полиномиальное время. 100% верно на всех наших экспериментах (включая формулы из SAT Comp). То есть всегда. Правда, во время своей работы он нарушал теорему из статьи, чего быть, конечно, не должно. Но это ошибка в теории, которая на практике не мешала никак. Еще одной проблемой этого solver'а (точнее самого алгоритма), являлась память — ее нужно было очень (полиномиально) много — поэтому на SAT Competitions с ним делать нечего.

Новому алгоритму не нужно столько памяти, и константа в полиноме там меньше, а значит теоретически он может работать на прикладных задачах большей размерности, и может быть с ним уже можно будет пойти на SAT Competitions.

Я не могу утверждать, что новая работа 100% верна, но если новый solver будет работать качественно также как предыдущий, только быстрее и потреблять меньше памяти — это уже будет хорошо.

Алгоритмы и структуры данных поиска. Лекции и курсы от Яндекса

А можно как-то выложить эти видео на iTunesU?

Зачем нам всем нужен SAT и все эти P-NP (часть первая)

Теоремы о невыразимости: почему статью Романова [3] ожидает reject

[3] Открытое письмо ученым и эталонная реализация алгоритма Романова для NP-полной задачи 3-ВЫП

Это не самая последняя версия работы Романова. Ошибку мы в ней нашли достаточно быстро после публикации. Очень помогла готовая реализация и тестовые наборы, которые мы нашли в SAT Competitions.

Недавно Владимир Федорович опубликовал продолжение своей работы:

romvf.wordpress.com/2013/09/25/development-of-the-concept/

В ней удалось избавиться от той части алгоритма, в которой была ошибка — от гиперструктур.
Хотя, это именно развитие предыдущей работы, поскольку многие положения остаются теми же.

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

Бесплатное программное обеспечение от JetBrains для образовательных учреждений

Это не совсем альтернатива, если Вы, конечно, не какой-нибудь Kohsuke Kawaguchi или один из тех парней, которые подходят под это описание:

You are the project lead or a committer
You have been working on your open source project for a minimum of 3 months
Your community is active. This means that you have recent activity in your newsgroups or forums
You have an updated News section on your site
You release updated builds on a regular basis

Сколько стоит создать приложение или вся правда о деньгах

Хорошая статья, правда немного популяризированная, потому что все расчеты в деньгах.

Все-таки рейты у всех немного отличаются, поэтому, на мой взгляд, было бы не плохо показать в основной табличке не только деньги, но и примерные трудозатраты в часах и показать сколько затрат в процентах на какой вид работ приходится (WBS).

И еще интересно сколько на вашем проекте это получилось в календарных днях (на сколько вы смогли распараллелить работы и как праздники и выходные на срок повлияли).

Еще тестирования не хватает в списке, оно, скорее всего, вошло в Программирование у вас, да?

Вышел Twitter Bootstrap 2.1.0

Как обычно, порт для SAAS можно найти здесь:

github.com/yury/bootstrap

и gem для rails:

github.com/anjlab/bootstrap-rails

Вышел AnjLab SQL Profiler 1.2

Затянул с ответом, конечно, но, насколько я знаю, у них в профайлере нет аналога Performance Dashboard.

История создания интерактивной книги для iPad

Уже здесь: habrahabr.ru/blogs/i_am_advertising/138552/
Там еще есть видео, можно посмотреть как озвучка работает.

История создания интерактивной книги для iPad

Есть такая книжка в appstore.

Попробуйте, скажите ваше мнение. Статью про историю создания книжки опубликуем со дня на день.

Моделирование большого количества взаимодействующих друг с другом частиц

Фактическое количество операций можно посчитать, если делать counter++ на каждой итерации самого глубокого цикла (циклов, если их несколько на одном уровне). Например,

counter = 0;

for (int i...) {
for (int j...) {

if (...) {

for (k...) {
counter++;
}

} else {


counter++;
}
}
}

Сделайте эту штуку только для части, где ведется поиск соседей. Если у вас моделируется поведение частиц в итераций — 1) найти соседей, 2) применить физику, 3) отрисовать, и опять сначала с шага 1) — то нужно сделать только замер первого прохода шага 1, т.е. когда частицы еще находятся в перемешанном состоянии. Можно, конечно, привести и замеры для второго и следующих проходах, но они будут не так показательны.

Еще, третий алгоритм зависит не только от количества частиц, но и от площади распределения частиц и от плотности распределения. Можете эти цифры тоже привести?

Моделирование большого количества взаимодействующих друг с другом частиц

По вашим результатам времена работы второго и третьего алгоритмов растут одинаково линейно (с небольшим различием линейного коэффициента).

Можете привести сравнение скорости выполнения не в миллисекундах (тем более про железо ничего не сказано), а в количестве операций?

Еще было бы интересно посмотреть как изменится производительность алгоритмов от плотности распределения частиц?

Кстати, сложность алгоритма поиска соседей не может быть O(n), потому что количество пар соседей — это даже не линейная функция от n. То есть, чтобы найти все пары соседей среди n точек не достаточно n операций. Например, для четырех близко расположенных точек, количество пар соседей будет равно шести.

FYI:
Во втором или третьем номере журнала «Программные продукты и системы» (2012) выйдет статья «Алгоритм поиска ближайших соседей» применительно к SPH. Там будет алгоритм со сложностью O(N^2/k), где k > 2 зависит от распределения частиц в пространстве.

Там, например, есть такой эксперимент, где показано, что для поиска очередной пары соседей требуется в среднем 1,3 операции (точки равномерно распределены в квадрате при плотности частиц от 40 до 98 процентов, сторона квадрата от 50 до 100 точек, то есть n было в диапазоне от 2500 до 10000, радиус взаимодействия равен 5, k получилось в диапазоне от 10 до 20). Интересно было бы посмотреть на ваши цифры.

Bookmarklet для Free-lance.ru

Ну можно посмотреть все сразу на одной странице, а не тыкать много раз по каждой ссылке :)

Использование Play! framework в Gedit

Я вот тоже не совсем понял, о чем хотел сказать автор и о чем он мечтал.

Использование Play! framework в Gedit

В день по нескольку раз :)

Информация

В рейтинге
5,970-й
Откуда
Россия
Дата рождения
Зарегистрирован
Активность