Все правильно, да. Статья про полиномиальный алгоритм для 3-SAT.
Если алгоритм правильный — это бы означало, что P == NP, но доказать равенство — не цель статьи.
т.е. банально никто на самом деле не проверял, а не было ли предложено похожих и/или эквивалентных методов?
Не могу отвечать за Романова. Я не проверял. Думаю он тоже, но это только мое мнение.
Всех интересует, чем же она действительно отличается, иначе смысл заниматься её изучением?
Ну вот вы же разобрались, чем один алгоритм отличается от другого и выше тут привели.
Или это не вы разбирались, а прочитали в статье других авторов?
Я не разбирался в чем отличие, потому что сначала надо разобраться в этом алгоритме, прежде чем его сравнивать.
А чтобы хорошо разобраться, лучше его реализовать и протестировать. Мной пока этого сделано не было.
От Владимира Федоровича я тоже не слышал этого.
Со стороны всегда просто рассуждать, почему одну работу ждет провал, а другую успех.
Конечно, на весь ваш список «здравого смысла» у меня (и, я уверен, у Владимира Федоровича) есть положительные ответы, но дело даже не в этом.
Статья не претендует на доказательства P ?= NP, в ней просто предлагается алгоритм решения 3-SAT и предлагается новый взгляд на представление этой задачи в виде структур компактных троек, который никто за 40 лет не предлагал, поэтому и нет ссылок — это новая работа, новый подход. И новая NP-полная задача. Искать сходства или различия с существующими подходами и алгоритмами — это не то, чем занимался автор.
В последней работе, на которую вы приводите ссылку, вводятся еще структуры компактных пар и метод, который лежит в основе решения доработанного алгоритма, очень схож с подходами к решению 2-SAT. Но там, например, нет никаких графов, о которых вы пишете. Вы сами-то не разобрались в этой работе, просто ссылаетесь?
Я могу понять, что у вас (и остальных) нет желания разбираться в новой статье, пока даже Романов не исследовал свой подход на практике и не опубликовал результаты. Не исследовал, в частности, потому что нет прототипа. Но его пока нет, и нет только потому, что его просто некому написать. Все действительно так просто.
Я также соглашусь, что в статье нет формального описания алгоритма. Его не было и в прошлой работе, прототип для которой был написан несколько раз. Один, последний, написал я в свое свободное время, постоянно консультируясь с Владимиром Федоровичем в течение 3-х месяцев. Видимо, с этой статьей нужно работать так же… кто возьмется пока я занят? Контакты обеспечу.
Если говорить о статье, в ней приводится именно конструктивное доказательство алгоритма и, кстати, solver от предыдущей работы ни разу не дал ложного решения с практической точки зрения — если формула выполнима он давал выполняемый набор, если нет — набора, соответственно, не выдавалось. И все это за полиномиальное время. 100% верно на всех наших экспериментах (включая формулы из SAT Comp). То есть всегда. Правда, во время своей работы он нарушал теорему из статьи, чего быть, конечно, не должно. Но это ошибка в теории, которая на практике не мешала никак. Еще одной проблемой этого solver'а (точнее самого алгоритма), являлась память — ее нужно было очень (полиномиально) много — поэтому на SAT Competitions с ним делать нечего.
Новому алгоритму не нужно столько памяти, и константа в полиноме там меньше, а значит теоретически он может работать на прикладных задачах большей размерности, и может быть с ним уже можно будет пойти на SAT Competitions.
Я не могу утверждать, что новая работа 100% верна, но если новый solver будет работать качественно также как предыдущий, только быстрее и потреблять меньше памяти — это уже будет хорошо.
Теоремы о невыразимости: почему статью Романова [3] ожидает reject
[3] Открытое письмо ученым и эталонная реализация алгоритма Романова для NP-полной задачи 3-ВЫП
Это не самая последняя версия работы Романова. Ошибку мы в ней нашли достаточно быстро после публикации. Очень помогла готовая реализация и тестовые наборы, которые мы нашли в SAT Competitions.
Недавно Владимир Федорович опубликовал продолжение своей работы:
В ней удалось избавиться от той части алгоритма, в которой была ошибка — от гиперструктур.
Хотя, это именно развитие предыдущей работы, поскольку многие положения остаются теми же.
Готовой программной реализации этого подхода еще нет. Но, если хочется потратить время над исследованиями Романова, то лучше начать с актуальной работы.
Это не совсем альтернатива, если Вы, конечно, не какой-нибудь 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).
И еще интересно сколько на вашем проекте это получилось в календарных днях (на сколько вы смогли распараллелить работы и как праздники и выходные на срок повлияли).
Еще тестирования не хватает в списке, оно, скорее всего, вошло в Программирование у вас, да?
Фактическое количество операций можно посчитать, если делать 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). Интересно было бы посмотреть на ваши цифры.
Если алгоритм правильный — это бы означало, что P == NP, но доказать равенство — не цель статьи.
В чем противоречие? Может быть я не так выразился?
Не могу отвечать за Романова. Я не проверял. Думаю он тоже, но это только мое мнение.
Ну вот вы же разобрались, чем один алгоритм отличается от другого и выше тут привели.
Или это не вы разбирались, а прочитали в статье других авторов?
Я не разбирался в чем отличие, потому что сначала надо разобраться в этом алгоритме, прежде чем его сравнивать.
А чтобы хорошо разобраться, лучше его реализовать и протестировать. Мной пока этого сделано не было.
От Владимира Федоровича я тоже не слышал этого.
Конечно, на весь ваш список «здравого смысла» у меня (и, я уверен, у Владимира Федоровича) есть положительные ответы, но дело даже не в этом.
Статья не претендует на доказательства P ?= NP, в ней просто предлагается алгоритм решения 3-SAT и предлагается новый взгляд на представление этой задачи в виде структур компактных троек, который никто за 40 лет не предлагал, поэтому и нет ссылок — это новая работа, новый подход. И новая NP-полная задача. Искать сходства или различия с существующими подходами и алгоритмами — это не то, чем занимался автор.
В последней работе, на которую вы приводите ссылку, вводятся еще структуры компактных пар и метод, который лежит в основе решения доработанного алгоритма, очень схож с подходами к решению 2-SAT. Но там, например, нет никаких графов, о которых вы пишете. Вы сами-то не разобрались в этой работе, просто ссылаетесь?
Я могу понять, что у вас (и остальных) нет желания разбираться в новой статье, пока даже Романов не исследовал свой подход на практике и не опубликовал результаты. Не исследовал, в частности, потому что нет прототипа. Но его пока нет, и нет только потому, что его просто некому написать. Все действительно так просто.
Я также соглашусь, что в статье нет формального описания алгоритма. Его не было и в прошлой работе, прототип для которой был написан несколько раз. Один, последний, написал я в свое свободное время, постоянно консультируясь с Владимиром Федоровичем в течение 3-х месяцев. Видимо, с этой статьей нужно работать так же… кто возьмется пока я занят? Контакты обеспечу.
Если говорить о статье, в ней приводится именно конструктивное доказательство алгоритма и, кстати, solver от предыдущей работы ни разу не дал ложного решения с практической точки зрения — если формула выполнима он давал выполняемый набор, если нет — набора, соответственно, не выдавалось. И все это за полиномиальное время. 100% верно на всех наших экспериментах (включая формулы из SAT Comp). То есть всегда. Правда, во время своей работы он нарушал теорему из статьи, чего быть, конечно, не должно. Но это ошибка в теории, которая на практике не мешала никак. Еще одной проблемой этого solver'а (точнее самого алгоритма), являлась память — ее нужно было очень (полиномиально) много — поэтому на SAT Competitions с ним делать нечего.
Новому алгоритму не нужно столько памяти, и константа в полиноме там меньше, а значит теоретически он может работать на прикладных задачах большей размерности, и может быть с ним уже можно будет пойти на SAT Competitions.
Я не могу утверждать, что новая работа 100% верна, но если новый solver будет работать качественно также как предыдущий, только быстрее и потреблять меньше памяти — это уже будет хорошо.
habrahabr.ru/post/207112/#comment_7169344
Это не самая последняя версия работы Романова. Ошибку мы в ней нашли достаточно быстро после публикации. Очень помогла готовая реализация и тестовые наборы, которые мы нашли в SAT Competitions.
Недавно Владимир Федорович опубликовал продолжение своей работы:
romvf.wordpress.com/2013/09/25/development-of-the-concept/
В ней удалось избавиться от той части алгоритма, в которой была ошибка — от гиперструктур.
Хотя, это именно развитие предыдущей работы, поскольку многие положения остаются теми же.
Готовой программной реализации этого подхода еще нет. Но, если хочется потратить время над исследованиями Романова, то лучше начать с актуальной работы.
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).
И еще интересно сколько на вашем проекте это получилось в календарных днях (на сколько вы смогли распараллелить работы и как праздники и выходные на срок повлияли).
Еще тестирования не хватает в списке, оно, скорее всего, вошло в Программирование у вас, да?
Вышла статья: swsys.ru/index.php?page=article&id=3249
github.com/yury/bootstrap
и gem для rails:
github.com/anjlab/bootstrap-rails
Там еще есть видео, можно посмотреть как озвучка работает.
Попробуйте, скажите ваше мнение. Статью про историю создания книжки опубликуем со дня на день.
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). Интересно было бы посмотреть на ваши цифры.