Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
| | | | | | | | |
Посмотрите ещё более внимательно... 04.03.05 22:14 Число просмотров: 3619
Автор: Партизан Статус: Незарегистрированный пользователь
Отредактировано 06.03.05 17:54 Количество правок: 1
|
>>> Потом смотрим основную теорему №5. Там сказано, что число
>>> шагов алгоритма не может превышать m, число строк таблицы.
>> Не число шагов алгоритма, а число вариантов анализа
>> таблицы.
> Ну это я так для краткости обозвал. Ну хорошо, пусть будет
> число вариантов анализа таблицы.
> Но сложность каждого варианта нигде не раскрыта!
Каждый вариант - это фактически прохождение какой-либо ветви дерева
расщепления формулы.
Если ветвь дерева "закрылась" (исход 1 у Тельпиза),
т. е. не получили ни пустого дизъюнкта (нулевой вектор у Тельпиза),
ни выполняющего набора, то переходим к следующему варианту анализа.
При каждом варианте анализа до получения результата "невыполнимость"
или до получения первого выполняющего набора в резолюционном выводе
участвует какой-нибудь дополнительный дизъюнкт, который в предыдущих
вариантах (в предыдущих ветвях дерева) не участвовал, поэтому
количество вариантов анализа (количество пройденных ветвей в дереве
расщепления) ограничено не 2^n, а количеством дизъюнктов m.
Каждый анализ состоит из нескольких шагов. На каждом шаге анализируется
какая-либо переменная (столбец в таблице).
Всего переменных (столбцов) - n, значит количество шагов - не больше n.
Таким образом, при каждом анализе таблица просматривается не более
одного раза, сложность - не больше O(m*n), или если использовать разреженную
таблицу - O(l), где l - общее число вхождений всех переменных в формулу
(общее число непустых ячеек в таблице).
>>> Но во-первых m лежит в диапазон 0 <= m <= 2^n, где n
>>> - число переменных.
>> Решаем задачу ВЫП, её размеры - это не n.
> Ладно, сознаюсь. Я не знаю как измеряются размеры задачи
> ВЫП, расскажите если не сложно.
А тут не надо ни чего знать, или Вы КНФ никогда не видели? Какие у КНФ размеры?
Количество переменных - n,
количество дизъюнктов (клозов) - m,
общее число l вхождений всех переменных в формулу.
Для k-ВЫП ещё: k - максимальный размер дизъюнкта.
l в общем-то определяет длину всей формулы F, поэтому можно сказать,
что l - определяет размер формулы КНФ в целом.
Ясно, что l<=m*n, а конкретно для задачи k-ВЫП l<=m*k.
Если l сравнимо с m*n, т. е. близко к m*n (не знаю, бывает ли такое в
реальности), тогда можно хранить формулу КНФ в памяти в виде 2-мерной таблицы
размерами m*n, как это сделано у Тельпиза. Тогда и оценивать сложность можно
относительно произведения m*n.
Если же l много меньше m*n, тогда разумнее хранить КНФ в разреженной таблице,
её размеры как раз и определяются количеством непустых ячеек, т. е. числом l.
К тому же разреженная таблица и ускорит обработку - не надо будет
просматривать пустые ячейки, т. е. и время однократного прочтения всей
таблицы тоже будет пропорционально числу l.
> Но мне всетаки казалось что
> количество переменных - определяющий фактор. Т.к. верхняя
> граница скорости выполнения как раз и задается полным
> перебором 2^n вариантов.
Угу. Но сложность алгоритма нужно оценивать относительно размеров задачи.
Известно, что для k-ВЫП случайного вида некий "фазовый переход", в смысле
есть некое число, зависящее от k, что если m/n заметно превышает это число,
то вероятность того, что КНФ выполнима, резко падает, стремится к нулю.
Если m/n меньше этого числа, то, наоборот, скорее всего КНФ выполнима.
Для 3-ВЫП, если не ошибаюсь фазовый переход происходит при отношении m/n
равном чуть больше 4 (4.2 или 4.25 - не помню).
Т. е. реально m имеет размеры сравнимые с n. И если сложность решения
относительно n полиномиальна, тогда и относительно l будет полиномиальна,
если относительно n - экспоненциальна, тогда и относительно l будет
экспоненциальна.
Если, как Вы говорите, m экпоненциально зависит от n (что почти невероятно в
реальных задачах), тогда оценивать сложность задачи ВЫП относительно n -
неразумно. Да и сведение других NP-полных задач размера n к задаче ВЫП не
будет полиномиальным, что не есть правда.
Обычно, оценивают сложность решения ВЫП относительно m или l.
>> На каждом шаге анализа таблицы просматриваем один
>> столбец.
>> Следовательно на одном шаге просматривается не более m
>> ячеек таблицы. Для каждого варианта столбцы
>> просматриваются
>> последовательно, двигаясь в левую сторону,
>> следовательно
>> при каждом варианте анализа просматривается не больше
>> n столбцов и не больше m*n ячеек, то есть таблица
>> просматривается при каждом варианте не более одного
>> раза.
>> До получения ответа на вопрос о выполнимости таблицы
>> просматриваем её не более m раз.
> Ладно. Допустим на каждом шаге мы просматриваем один
> столбец.
> Тогда получается, что для каждого "вывода" нужно
> просмотреть всю таблицу.
Не "вывод", "вариант анализа" у Тельпиза, фактически - это прохождение
одной ветви дерева расщепления.
> Вывод - это выход на вариант 1-3. НО! выход на вариант 1 -
> это еще не конец "анализа"
У Тельпиза как раз выходом на исходы 1 или 2-3 и заканчивается
"текущий вариант анализа".
> таблицы, после получения варианта 1, мы должны снова
> проанализировать часть таблицы,
Пусть даже всю таблицу - O(l). Общее число этих вариантов анализа будет не
больше количества дизъюнктов m.
> а потом снова и снова. Нигде не показана сложность
> вытекающая из этой рекурсии.
См. теорему 5. Сложность O(m) * сложность одного варианта анализа, общая
сложность до находения первого выполняющего набора - O(m*l) или
O(m*m*n), если таблица неразрежена (т. е. хранятся и обрабатываются пустые
ячейки).
> А если внимательно присмотреться к приводимым примером
> легко можно заметить, что
> чаще всего происходит ПОЛНЫЙ перебор некоторого
> подмножества переменных, и только
> часть переменных отсеивается в дальнейшем.
Что Вы называете ПОЛНЫМ перебором некоторого подмножества переменных?
O(n) - это не экспоненциальная сложность. ;-)
Экспоненциальная сложность - это, например, ПОЛНЫЙ перебор
_всех_наборов_значений_ переменных O(2^n)
или подмножества переменных, в случае, если это
подмножество имеет размеры O(n).
Составление третьей служебной строки в процессе одного анализа
таблицы - это и есть фактически составление набора значений переменных:
на каждом шаге запись номера исхода 2, 4, T или 3, 5, T* в третью служебную
строку означает, что соответствующей переменной присваивается значение
1 или 0 (см. внизу страницы 14 ) и исключаются из рассмотрения
выполненные (принявшие значение =1) дизъюнкты (строки таблицы),
а в оставшихся вычёркивается эта переменная. Кроме исхода 6б - в этом случае
соответствующая переменная в набор не входит (т. е. получается неполный набор)
Причём расщепление формулы ("ветвление", "разбиение таблицы на две подтаблицы"
у Тельпиза) осуществляется только при выходе на исход 6б, а при исходах 4 и 5, 6а
ветвления не происходит.
Посмотрите ещё более внимательно: где-нибудь количество вариантов анализа,
а значит и число рассмотренных наборов превышает m?
Чтобы доказать, что Тельпиз неправ, достаточно придумать пример простейшей
таблицы, на которой его алгоритм будет давать больше, чем m вариантов анализа,
или будет зацикливаться...
Кстати, вот ссылка на работу (институт Стеклова) 2001 года , где описаны и
проанализированы на русском языке некоторые алгоритмы выполнимости:
http://cs.roosevelt.edu/~dantsin/ps/DHIV01b.ps
|
|
<site updates>
|
Факторизация (factoring) и выполнимость (satisfability) 13.11.04 22:54
Publisher: dl <Dmitry Leonov>
|
Факторизация (factoring) и выполнимость (satisfability)
lime http://www.bugtraq.ru/cgi-bin/iforum.mcgi?type=si&u=7098
Представление.
Факторизация - разложение целого числа на два целых множителя.
Обозначим числа, которыми будем оперировать следующим образом: Z = X*Y.
С самого начала следует определиться с тем, в каком виде следует представить числа. Ответ очевиден - в двоичной. Именно эта система счисления дает желаемые исходные значения логических переменных - нули и единицы.
Заранее договоримся, что исходные числа будем обозначать заглавными буквами, а их разряды - прописными.
Таким образом, исходное выражение Z = X*Y примет вид z1z2z3...zn = x1x2x3...xn * y1y2y3...yn.
Разрядность всех чисел одинакова не случайно. Это единственный способ получить ВСЕ ВОЗМОЖНЫЕ РАЗЛОЖЕНИЯ исходного числа вплоть до тривиального, когда один из сомножителей равен 1. В качестве отступления можно сказать, что в случае, если мы хотим получить все возможный разложения, за исключением тривиального, следует вспомнить,...
Полный текст
|
|
О полиномиальной сложности факторизации и о теории М. И. Тельпиза 19.12.04 00:09
Автор: Партизан Статус: Незарегистрированный пользователь
Отредактировано 20.12.04 01:50 Количество правок: 3
|
>Более изощренные алгоритмы минимизируют сложность до значения O(n^1,5).
Вы не могли бы указать ссылку на такой алгоритм или привести его?
Кстати, на сайте http://www.tarusa.ru/~mit утверждается, что доказано P=NP.
Упомянутая на том сайте книга продаётся в Интернете:
http://urss.ru/cgi-bin/db.pl?page=Book&id=24175&lang=Ru
Задача ВЫП с нахождением выполняющих наборов решается за линейное время.
Люди использующие теорию Мирона Тельпиза утверждают, что числа длиной 1024 бита факторизуются за минуты со сложностью не более O(n^2).
|
| |
Есть очень большое количество алгоритмов быстрого умножения... 28.12.04 08:56
Автор: lime Статус: Незарегистрированный пользователь
Отредактировано 28.12.04 08:57 Количество правок: 1
|
> Вы не могли бы указать ссылку на такой алгоритм или
> привести его?
Есть очень большое количество алгоритмов быстрого умножения. Сейчас навскидку могу сказать, что 1,5 - это, если я не ошибаюсь, алгориитм Карацубы.
> Кстати, на сайте http://www.tarusa.ru/~mit утверждается,
> что доказано P=NP.
> Упомянутая на том сайте книга продаётся в Интернете:
> http://urss.ru/cgi-bin/db.pl?page=Book&id=24175&lang=Ru
> Задача ВЫП с нахождением выполняющих наборов решается за
> линейное время.
> Люди использующие теорию Мирона Тельпиза утверждают, что
> числа длиной 1024 бита факторизуются за минуты со
> сложностью не более O(n^2).
Наблюдаю уже несколько лет за этой темой :) Даже помнится письмо писал, узнавал как дела обстоят с практической реализацией. В ответ получил примерное следующее "Практической реализации - никакой, а позицирнная алгебра развивается" :)
Я бы с удовольствием познакомился с "людьми, использующими теорию Мирона Тельпиза" с тем, чтобы получить фактическое подтверждение того, о чем говорится.
Кроме того очень меня улыбает вот это: http://www.tarusa.ru/~mit/RUS/atten.php Работа, якобы, закончена, но нужны деньги, чтобы дальше двигаться :)
|
| | |
Тельпиз 05.01.05 18:22
Автор: Партизан Статус: Незарегистрированный пользователь
|
> Наблюдаю уже несколько лет за этой темой :) Даже помнится
> письмо писал, узнавал как дела обстоят с практической
> реализацией. В ответ получил примерное следующее
> "Практической реализации - никакой, а позицирнная алгебра
> развивается" :)
> Я бы с удовольствием познакомился с "людьми, использующими
> теорию Мирона Тельпиза" с тем, чтобы получить фактическое
> подтверждение того, о чем говорится.
> Кроме того очень меня улыбает вот это:
> http://www.tarusa.ru/~mit/RUS/atten.php Работа, якобы,
> закончена, но нужны деньги, чтобы дальше двигаться :)
А не пытались ли Вы найти ошибку в доказательстве у Тельпиза? Хотя бы в той статье про 4 краски?
|
| | | |
А как Вы думаете, если тот, кто ведет этот проект говорит,... 01.02.05 07:18
Автор: lime Статус: Незарегистрированный пользователь
|
> А не пытались ли Вы найти ошибку в доказательстве у
> Тельпиза? Хотя бы в той статье про 4 краски?
А как Вы думаете, если тот, кто ведет этот проект говорит, что практическая реализация отсутствует, есть резон это делать? :)
|
| | | | |
Есть ли ошибки у Тельпиза? 02.02.05 22:43
Автор: Партизан Статус: Незарегистрированный пользователь
|
> > А не пытались ли Вы найти ошибку в доказательстве у
> > Тельпиза? Хотя бы в той статье про 4 краски?
>
> А как Вы думаете, если тот, кто ведет этот проект говорит,
> что практическая реализация отсутствует, есть резон это
> делать? :)
Какая Вам нужна реализация?
http://www.tarusa.ru/~mit/RUS/sup_prim1.php:
"На базе позиционной нотации доказано, что классы P и NP совпадают, создан программный продукт (ПП), который позволяет практически решать задачи из класса NP, но с трудностями, присущими уже классу P."
Обратите внимание: говорится, что создан программный продукт.
Там далее приведён пример.
В книге (купить можно по этой ссылке: http://urss.ru/cgi-bin/db.pl?page=Book&id=24175&lang=Ru) тоже говорится о программных продуктах (см. параграф 8.14), которые, как я понимаю, созданы А. А. Фоминым. Спросить о них, как я понимаю, можно по адресу mit@tarusa.ru
|
| | | | | |
Ошибки есть, и видно их невооруженным взглядом. 09.02.05 12:53
Автор: NickP Статус: Незарегистрированный пользователь
|
> > > А не пытались ли Вы найти ошибку в доказательстве
> у
> > > Тельпиза? Хотя бы в той статье про 4 краски?
Вот прочитал я эту статью, и первое что мне бросилось в глаза, это практические результаты приведенные самим Тельпизом. Цитата:
"Вся задача имеет 144 переменных и 644 строки и ее суперприведение выполняется за 6 мин 45 секунд (Pentium-866). Суперприведение же каждого блока [~50 переменных, ~215 строк] составляет 3, 5 и 6 сек".
Кто тутговорил про 1024 бита за минуты? И где тут полиномиальная зависимость?
Потом смотрим основную теорему №5. Там сказано, что число шагов алгоритма не может превышать m, число строк таблицы.
Но во-первых m лежит в диапазон 0 <= m <= 2^n, где n - число переменных.
А во-вторых, нигде не показанно как каждый шаг алгоритма зависит от n и m. А зависимость там явно не полиномиальная.
|
| | | | | | |
Вы уверены, что ошибки действительно есть? 17.02.05 19:06
Автор: Партизан Статус: Незарегистрированный пользователь
|
> > > > А не пытались ли Вы найти ошибку в
> доказательстве
> > у
> > > > Тельпиза? Хотя бы в той статье про 4 краски?
>
> Вот прочитал я эту статью, и первое что мне бросилось в
> глаза, это практические результаты приведенные самим
> Тельпизом. Цитата:
> "Вся задача имеет 144 переменных и 644 строки и ее
> суперприведение выполняется за 6 мин 45 секунд
> (Pentium-866). Суперприведение же каждого блока [~50
> переменных, ~215 строк] составляет 3, 5 и 6 сек".
> Кто тутговорил про 1024 бита за минуты? И где тут
> полиномиальная зависимость?
Я имел в виду другую программу другого автора.
> Потом смотрим основную теорему №5. Там сказано, что число
> шагов алгоритма не может превышать m, число строк таблицы.
Не число шагов алгоритма, а число вариантов анализа таблицы.
> Но во-первых m лежит в диапазон 0 <= m <= 2^n, где n
> - число переменных.
Решаем задачу ВЫП, её размеры - это не n.
Если решаем другую NP-полную задачу, то она должна полиномиально сводиться к ВЫП.
> А во-вторых, нигде не показанно как каждый шаг алгоритма
> зависит от n и m. А зависимость там явно не полиномиальная.
На каждом шаге анализа таблицы просматриваем один столбец. Следовательно на одном шаге просматривается не более m ячеек таблицы. Для каждого варианта столбцы просматриваются последовательно, двигаясь в левую сторону, следовательно при каждом варианте анализа просматривается не больше n столбцов и не больше m*n ячеек, то есть таблица просматривается при каждом варианте не более одного раза. До получения ответа на вопрос о выполнимости таблицы просматриваем её не более m раз.
|
| | | | | | | |
Ну это я так для краткости обозвал. Ну хорошо, пусть будет... 04.03.05 15:06
Автор: NickP Статус: Незарегистрированный пользователь
|
> > Потом смотрим основную теорему №5. Там сказано, что
> число
> > шагов алгоритма не может превышать m, число строк
> таблицы.
>
> Не число шагов алгоритма, а число вариантов анализа
> таблицы.
Ну это я так для краткости обозвал. Ну хорошо, пусть будет число вариантов анализа таблицы.
Но сложность каждого варианта нигде не раскрыта!
> > Но во-первых m лежит в диапазон 0 <= m <= 2^n,
> где n
> > - число переменных.
>
> Решаем задачу ВЫП, её размеры - это не n.
Ладно, сознаюсь. Я не знаю как измеряются размеры задачи ВЫП, расскажите если не сложно. Но мне всетаки казалось что количество переменных - определяющий фактор. Т.к. верхняя граница скорости выполнения как раз и задается полным перебором 2^n вариантов.
> На каждом шаге анализа таблицы просматриваем один столбец.
> Следовательно на одном шаге просматривается не более m
> ячеек таблицы. Для каждого варианта столбцы просматриваются
> последовательно, двигаясь в левую сторону, следовательно
> при каждом варианте анализа просматривается не больше n
> столбцов и не больше m*n ячеек, то есть таблица
> просматривается при каждом варианте не более одного раза.
> До получения ответа на вопрос о выполнимости таблицы
> просматриваем её не более m раз.
Ладно. Допустим на каждом шаге мы просматриваем один столбец.
Тогда получается, что для каждого "вывода" нужно просмотреть всю таблицу.
Вывод - это выход на вариант 1-3. НО! выход на вариант 1 - это еще не конец "анализа"
таблицы, после получения варианта 1, мы должны снова проанализировать часть таблицы,
а потом снова и снова. Нигде не показана сложность вытекающая из этой рекурсии.
А если внимательно присмотреться к приводимым примером легко можно заметить, что
чаще всего происходит ПОЛНЫЙ перебор некоторого подмножества переменных, и только
часть переменных отсеивается в дальнейшем.
|
| | | | | | | | |
Посмотрите ещё более внимательно... 04.03.05 22:14
Автор: Партизан Статус: Незарегистрированный пользователь
Отредактировано 06.03.05 17:54 Количество правок: 1
|
>>> Потом смотрим основную теорему №5. Там сказано, что число
>>> шагов алгоритма не может превышать m, число строк таблицы.
>> Не число шагов алгоритма, а число вариантов анализа
>> таблицы.
> Ну это я так для краткости обозвал. Ну хорошо, пусть будет
> число вариантов анализа таблицы.
> Но сложность каждого варианта нигде не раскрыта!
Каждый вариант - это фактически прохождение какой-либо ветви дерева
расщепления формулы.
Если ветвь дерева "закрылась" (исход 1 у Тельпиза),
т. е. не получили ни пустого дизъюнкта (нулевой вектор у Тельпиза),
ни выполняющего набора, то переходим к следующему варианту анализа.
При каждом варианте анализа до получения результата "невыполнимость"
или до получения первого выполняющего набора в резолюционном выводе
участвует какой-нибудь дополнительный дизъюнкт, который в предыдущих
вариантах (в предыдущих ветвях дерева) не участвовал, поэтому
количество вариантов анализа (количество пройденных ветвей в дереве
расщепления) ограничено не 2^n, а количеством дизъюнктов m.
Каждый анализ состоит из нескольких шагов. На каждом шаге анализируется
какая-либо переменная (столбец в таблице).
Всего переменных (столбцов) - n, значит количество шагов - не больше n.
Таким образом, при каждом анализе таблица просматривается не более
одного раза, сложность - не больше O(m*n), или если использовать разреженную
таблицу - O(l), где l - общее число вхождений всех переменных в формулу
(общее число непустых ячеек в таблице).
>>> Но во-первых m лежит в диапазон 0 <= m <= 2^n, где n
>>> - число переменных.
>> Решаем задачу ВЫП, её размеры - это не n.
> Ладно, сознаюсь. Я не знаю как измеряются размеры задачи
> ВЫП, расскажите если не сложно.
А тут не надо ни чего знать, или Вы КНФ никогда не видели? Какие у КНФ размеры?
Количество переменных - n,
количество дизъюнктов (клозов) - m,
общее число l вхождений всех переменных в формулу.
Для k-ВЫП ещё: k - максимальный размер дизъюнкта.
l в общем-то определяет длину всей формулы F, поэтому можно сказать,
что l - определяет размер формулы КНФ в целом.
Ясно, что l<=m*n, а конкретно для задачи k-ВЫП l<=m*k.
Если l сравнимо с m*n, т. е. близко к m*n (не знаю, бывает ли такое в
реальности), тогда можно хранить формулу КНФ в памяти в виде 2-мерной таблицы
размерами m*n, как это сделано у Тельпиза. Тогда и оценивать сложность можно
относительно произведения m*n.
Если же l много меньше m*n, тогда разумнее хранить КНФ в разреженной таблице,
её размеры как раз и определяются количеством непустых ячеек, т. е. числом l.
К тому же разреженная таблица и ускорит обработку - не надо будет
просматривать пустые ячейки, т. е. и время однократного прочтения всей
таблицы тоже будет пропорционально числу l.
> Но мне всетаки казалось что
> количество переменных - определяющий фактор. Т.к. верхняя
> граница скорости выполнения как раз и задается полным
> перебором 2^n вариантов.
Угу. Но сложность алгоритма нужно оценивать относительно размеров задачи.
Известно, что для k-ВЫП случайного вида некий "фазовый переход", в смысле
есть некое число, зависящее от k, что если m/n заметно превышает это число,
то вероятность того, что КНФ выполнима, резко падает, стремится к нулю.
Если m/n меньше этого числа, то, наоборот, скорее всего КНФ выполнима.
Для 3-ВЫП, если не ошибаюсь фазовый переход происходит при отношении m/n
равном чуть больше 4 (4.2 или 4.25 - не помню).
Т. е. реально m имеет размеры сравнимые с n. И если сложность решения
относительно n полиномиальна, тогда и относительно l будет полиномиальна,
если относительно n - экспоненциальна, тогда и относительно l будет
экспоненциальна.
Если, как Вы говорите, m экпоненциально зависит от n (что почти невероятно в
реальных задачах), тогда оценивать сложность задачи ВЫП относительно n -
неразумно. Да и сведение других NP-полных задач размера n к задаче ВЫП не
будет полиномиальным, что не есть правда.
Обычно, оценивают сложность решения ВЫП относительно m или l.
>> На каждом шаге анализа таблицы просматриваем один
>> столбец.
>> Следовательно на одном шаге просматривается не более m
>> ячеек таблицы. Для каждого варианта столбцы
>> просматриваются
>> последовательно, двигаясь в левую сторону,
>> следовательно
>> при каждом варианте анализа просматривается не больше
>> n столбцов и не больше m*n ячеек, то есть таблица
>> просматривается при каждом варианте не более одного
>> раза.
>> До получения ответа на вопрос о выполнимости таблицы
>> просматриваем её не более m раз.
> Ладно. Допустим на каждом шаге мы просматриваем один
> столбец.
> Тогда получается, что для каждого "вывода" нужно
> просмотреть всю таблицу.
Не "вывод", "вариант анализа" у Тельпиза, фактически - это прохождение
одной ветви дерева расщепления.
> Вывод - это выход на вариант 1-3. НО! выход на вариант 1 -
> это еще не конец "анализа"
У Тельпиза как раз выходом на исходы 1 или 2-3 и заканчивается
"текущий вариант анализа".
> таблицы, после получения варианта 1, мы должны снова
> проанализировать часть таблицы,
Пусть даже всю таблицу - O(l). Общее число этих вариантов анализа будет не
больше количества дизъюнктов m.
> а потом снова и снова. Нигде не показана сложность
> вытекающая из этой рекурсии.
См. теорему 5. Сложность O(m) * сложность одного варианта анализа, общая
сложность до находения первого выполняющего набора - O(m*l) или
O(m*m*n), если таблица неразрежена (т. е. хранятся и обрабатываются пустые
ячейки).
> А если внимательно присмотреться к приводимым примером
> легко можно заметить, что
> чаще всего происходит ПОЛНЫЙ перебор некоторого
> подмножества переменных, и только
> часть переменных отсеивается в дальнейшем.
Что Вы называете ПОЛНЫМ перебором некоторого подмножества переменных?
O(n) - это не экспоненциальная сложность. ;-)
Экспоненциальная сложность - это, например, ПОЛНЫЙ перебор
_всех_наборов_значений_ переменных O(2^n)
или подмножества переменных, в случае, если это
подмножество имеет размеры O(n).
Составление третьей служебной строки в процессе одного анализа
таблицы - это и есть фактически составление набора значений переменных:
на каждом шаге запись номера исхода 2, 4, T или 3, 5, T* в третью служебную
строку означает, что соответствующей переменной присваивается значение
1 или 0 (см. внизу страницы 14 ) и исключаются из рассмотрения
выполненные (принявшие значение =1) дизъюнкты (строки таблицы),
а в оставшихся вычёркивается эта переменная. Кроме исхода 6б - в этом случае
соответствующая переменная в набор не входит (т. е. получается неполный набор)
Причём расщепление формулы ("ветвление", "разбиение таблицы на две подтаблицы"
у Тельпиза) осуществляется только при выходе на исход 6б, а при исходах 4 и 5, 6а
ветвления не происходит.
Посмотрите ещё более внимательно: где-нибудь количество вариантов анализа,
а значит и число рассмотренных наборов превышает m?
Чтобы доказать, что Тельпиз неправ, достаточно придумать пример простейшей
таблицы, на которой его алгоритм будет давать больше, чем m вариантов анализа,
или будет зацикливаться...
Кстати, вот ссылка на работу (институт Стеклова) 2001 года , где описаны и
проанализированы на русском языке некоторые алгоритмы выполнимости:
http://cs.roosevelt.edu/~dantsin/ps/DHIV01b.ps
|
| | | | | | | | | |
Вот именно, что внимателней 09.03.05 13:08
Автор: NickP Статус: Незарегистрированный пользователь
|
> У Тельпиза как раз выходом на исходы 1 или 2-3 и
> заканчивается
> "текущий вариант анализа".
"Текущий вариант анализа" заканчивается, только выходом на вариант 2-3 или при получении 0 в варианте 1.
Все остальные выходы на вариант 1 приводят к рекурсии.
> > таблицы, после получения варианта 1, мы должны снова
> > проанализировать часть таблицы,
>
> Пусть даже всю таблицу - O(l). Общее число этих вариантов
> анализа будет не
> больше количества дизъюнктов m.
Откуда это следует?
> > А если внимательно присмотреться к приводимым примером
> > легко можно заметить, что
> > чаще всего происходит ПОЛНЫЙ перебор некоторого
> > подмножества переменных, и только
> > часть переменных отсеивается в дальнейшем.
>
> Что Вы называете ПОЛНЫМ перебором некоторого подмножества
> переменных?
> O(n) - это не экспоненциальная сложность. ;-)
Ну вот в таблице 1, явно идет полный перебор значений переменных 4,5. Для 6 переменных это довольно много. Если для каждых n переменных мы будем иметь k = n/3 которые будут перебираться полностью, то где-же тут полимиальная сложность?
Ну даже, если это будет и не n/3, но все равно значительная чать переменных, мы полимиальной сложности не получим.
|
| | | | | | | | | | |
Рецензия на статью М. И. Тельпиза “NP-полнота, суперприведение и проблема четырех красок” 23.03.05 00:18
Автор: Партизан Статус: Незарегистрированный пользователь
|
|
На сайте http://satisfiability.narod.ru/index.html есть рецензия на статью М. И. Тельпиза “NP-полнота, суперприведение и проблема четырех красок”
|
| | | | | | | | | | |
Вот именно, что внимателней ;-) 09.03.05 20:35
Автор: Партизан Статус: Незарегистрированный пользователь
|
> > У Тельпиза как раз выходом на исходы 1 или 2-3 и
> > заканчивается
> > "текущий вариант анализа".
Стр. 13 статьи:
"Перед тем, как перейти к анализу ведущего столбца
с номером k - 1 (к такому анализу переходим лишь
в том случае, когда номер исхода для k-того столбца
больше 3)...".
Т. е. текщий анализ продолжается только при номерах
исходов больше 3. При исходах 1-3 текущий анализ
заканчивается (заканчивается построение набора в
третьей служебной строке, т. е. имеем здесь лист в дереве
расщепления исходной формулы). Посмотрите хотя бы
примеры - видно же, что везде третья служебная
заканчивает заполняться справа налево при исходах 1-3.
> "Текущий вариант анализа" заканчивается, только выходом на
> вариант 2-3
Выходом на варианты 2-3 вообще-то заканчивается
решение задачи выполнимости, т. к. при этих
исходах имеем выполнимость и даже построенный
выполняющий набор. Дальнейший анализ в этом
случае - это уже не решение задачи выполнимости,
а поиск остальных выполняющих наборов.
> или при получении 0 в варианте 1.
При получении 0 для всей исходной формулы опять
же заканчивается не текущий анализ, а вообще поиск
выполняющих наборов, т. к. если формула
тождественно равна нулю, значит выполняющих
наборов для неё больше нет.
> Все остальные выходы на вариант 1 приводят к рекурсии.
Все остальные выходы на вариант 1 - это
"локальный 0", т. е. 0 только для анализируемой на
данном шаге подтаблицы (с исключёнными строками
и столбцами) и это означает, что дальнейшее
построение набора (т. е. дальнейшее заполнение
третьей служебной строки) не имеет смысла, т. к.
уже при текущем неполном наборе ясно, что здесь
выполнимого набора не найдём и надо что-то менять
в этом текущем наборе, а меняем значение в одном
из тех столбцов, который является столбцом
ветвления (исход 6б), и после этого в этом столбце
ветвления не будет, а именно, в этом столбце
меняется T на 5 или T* на 4, а в каком из столбцов
ветвления менять значение - определяется при
помощи построения резолюций: если
результирующая резольвента не будет равна нулю,
то начало этого резолюционного вектора и
покажет, в каком столбце поменяется значение
и с этого столбца продолжится уже следующий
вариант анализа и с этого столбца изменится
следующая третья служебная строка.
> > > таблицы, после получения варианта 1, мы должны
> > > снова проанализировать часть таблицы,
> > Пусть даже всю таблицу - O(l). Общее число этих
> > вариантов анализа будет не
> > больше количества дизъюнктов m.
> Откуда это следует?
Это имелось в виду до нахождения первого выполняющего
набора, или получения невыполнимости для всей исходной
анализируемой таблицы.
При каждом варианте анализа, когда он заканчивается
исходом 1, у нас имеются векторы (а значит и дизъюнкты),
помеченные звёздочкой. Звёздочкой помечаем по одному
вектору, который приводил нас к исходам 4 или 5
(т .е. когда по анализируемой переменной не получаем
ветвления), а также помечаем звёздочкой пару векторов,
приведшую к исходу 1. Те из векторов, помеченных звёздочкой,
которые потребуются на этапе вычисления резолюций,
войдут в минимальный согласованный сегмент.
Т. е. количество этих минимальных согласованных
сегментов - количество вариантов анализа.
Дальше см. стр. 28, там доказательство того, что количество
этих сегментов не может быть больше числа m - количества
строк исходной таблицы (количества дизъюнктов исходной формулы).
> > > А если внимательно присмотреться к приводимым
> > > примером
> > > легко можно заметить, что
> > > чаще всего происходит ПОЛНЫЙ перебор некоторого
> > > подмножества переменных, и только
> > > часть переменных отсеивается в дальнейшем.
> > Что Вы называете ПОЛНЫМ перебором некоторого
> > подмножества переменных?
> > O(n) - это не экспоненциальная сложность. ;-)
> Ну вот в таблице 1, явно идет полный перебор значений
> переменных 4,5. Для 6 переменных это довольно много.
Немного.
Перебор по двум переменным - это 2^2 = 4
Перебор по 6 переменным - это 2^6 = 64, в 16 раз больше.
Всё равно, общее количество вариантов анализа (количество
третьих служебных строк, количество построенных наборов)
равно 10, а количество строк в исходной таблице (количество
дизъюнктов в исходной формуле КНФ) равно 28.
10 <= 28, так что всё сходится с утверждениями о сложности.
> Если
> для каждых n переменных мы будем иметь k = n/3 которые
> будут перебираться полностью, то где-же тут полимиальная
> сложность?
> Ну даже, если это будет и не n/3, но все равно значительная
> чать переменных, мы полимиальной сложности не получим.
Число m, как я упоминал, для k-ВЫП реальных задач обычно
приблизительно пропорционально числу n, и коэффициент
пропорциональности зависит от k.
Допустим, задача 3-ВЫП, и 1000 переменных и 4096 дизъюнктов.
Значит, количество строк в исходной таблице - 4096, количество
столбцов - 1000, и, если верить Тельпизу, количество минимальных
согласованных сегментов (количество вариантов анализа
таблицы) будет не больше 4096, т. о. получается, что может
быть не больше 12 переменных, по которым может произойти
полный перебор. Т. е. количество переменных, по которым
может произойти полный перебор, может возрастать в среднем
не быстрее чем log от m, а значит и log от n.
Зависимость не пропорциональная, а логарифмическая.
|
| | | | | |
Да, это очень хороший пример. Большей воды я не встречал. 03.02.05 09:49
Автор: lime Статус: Незарегистрированный пользователь
Отредактировано 03.02.05 09:49 Количество правок: 1
|
> Какая Вам нужна реализация?
> http://www.tarusa.ru/~mit/RUS/sup_prim1.php:
> "На базе позиционной нотации доказано, что классы P и NP
> совпадают, создан программный продукт (ПП), который
> позволяет практически решать задачи из класса NP, но с
> трудностями, присущими уже классу P."
> Обратите внимание: говорится, что создан программный
> продукт.
> Там далее приведён пример.
Да, это очень хороший пример. Большей воды я не встречал.
Для начала. "Вот простой пример. Допустим спроектировано электронное устройство, состоящее из трех блоков, каждый из которых содержит 50 элементов и соединен с последующим посредством трех общих элементов. Представим данное устройство в логическом виде в форме задачи ВЫП. "
Хочу сказать, что это не простой пример хотя бы потому, что я не могу понять при чем здесь "электронное устройиство...из трех блоков". Не проще ли показать простую формулу ВЫП.
Далее.
"Каков результат применения суперприведения? 1) Сокращен размер исходной КНФ более, чем в 2 раза, а значит и размер самого электронного устройства. При этом выполняющие наборы не изменились, т.е. не изменился проектный замысел устройства. 2) В результате выполненной реструктуризации выполняющие наборы будут срабатывать по мере поступления запроса на них, т.е. полностью исключается время обработки холостых или подготовительных вычислений, какие имели бы место в исходном варианте. А это уже даст многократный прирост скорости работы по сравнению с исходным вариантом. "
Это, извините, не решение задачи ВЫП, а минимизация логической формулы. :)
И в заключении.
Решение проблемы NP-полноты заключается в отыскании полиномиального алгоритма для решения любой из NP-полных задач в общем виде. Т.е. для доказательства надо представить алгоритм и показать, что рост его сложности не экспоненциален по входным данным для задачи любого вида. Представить алгоритм для единственной задачи частного вида - это не проблема.
По поводу "программного продукта". Я его не видел и не работал с ним. А на слово я верить не буду.
И последнее. С трудом верится, что люди имеющие, по их словам методику решения, стОящую по авторитетным оценкам сотни миллиардов долларов пытаются найти деньги на "продолжение работ", а зарабатывают продажей книг. :)
Это не научный подход. Скорее смахивает на дешевый журналистский PR, устроенный с целью поднять шумиху и выдоить из этой ситуации максимум.
Теперь по поводу Вашего вопроса, упомянутого в заголовке. Я не знаю. Вся обстановка, с которой это обставлено, не располагает меня разбираться с этим вопросом. Но по "мебелировке" можно сделать вывод, что ответ будет скорее нет, чем да. Я пожалуй ознакомился бы с простым и понятным примером решения задачи ВЫП, изложенным ясно и без "электронных устройств на три блока", но его к сожалению нет.
> В книге (купить можно по этой ссылке:
> http://urss.ru/cgi-bin/db.pl?page=Book&id=24175&lang=Ru)
> тоже говорится о программных продуктах (см. параграф 8.14),
> которые, как я понимаю, созданы А. А. Фоминым. Спросить о
> них, как я понимаю, можно по адресу mit@tarusa.ru
Вот как раз по этому адресу я отправил свой вопрос. О результатах сообщил выше. :)
|
| | | | | | |
Полиномиальный алгоритм для задачи ВЫП 17.02.05 19:14
Автор: Партизан Статус: Незарегистрированный пользователь
|
> Решение проблемы NP-полноты заключается в отыскании
> полиномиального алгоритма для решения любой из NP-полных
> задач в общем виде.
В статье "NP-полнота, суперприведение и проблема четырёх красок" приведён полиномиальный алгоритм для решения задачи ВЫП и показано, что для ответа о выполнимости или невыполнимости нужно просмотреть таблицу не более m раз, где m - число строк в таблице ВЫП.
> Т.е. для доказательства надо
> представить алгоритм и показать, что рост его сложности не
> экспоненциален по входным данным для задачи любого вида.
Другие NP-полные задачи полиномиально сводятся к ВЫП.
> Представить алгоритм для единственной задачи частного вида
> - это не проблема.
Там представлен алгоритм для задачи ВЫП общего вида.
|
| | | | | | |
Кстати, могу привести место, где можно получить первый миллион баксов на продолжение исследований 04.02.05 11:30
Автор: amirul <Serge> Статус: The Elderman
|
> > "На базе позиционной нотации доказано, что классы P и
> NP
> > совпадают, создан программный продукт (ПП), который
> И последнее. С трудом верится, что люди имеющие, по их
> словам методику решения, стОящую по авторитетным оценкам
> сотни миллиардов долларов пытаются найти деньги на
> "продолжение работ", а зарабатывают продажей книг. :)
Согласен
http://www.claymath.org/millennium/
http://www.claymath.org/millennium/P_vs_NP/
|
|
Не совсем понятно 14.11.04 00:44
Автор: Heller <Heller> Статус: Elderman
|
Во-первых, совершенно неясно как помогает представленная форма сведения факторизовать произвольное n.
Во-вторых, в статье я нигде не нашёл, откуда следует, что сложность будет именно O(n^2), а не как-то по-другому.
Вообще написано достаточно пространно и если я правильно понял статью, то автором предлагается свести конкретное число к логическому высказыванию, откуда найти сомножители. Хотя это я уже сам домыслил (а по-другому вообще непонятно как факторизировать, опираясь на приведённый текст). Однако, если следуя подобным рассуждениям попытаться прописать термы для числа длиной по-больше, то вообще делается видно, что количество переменных и логических переменных возрастает гораздо быстрее, чем функция x^2. Т. к. для факторизации никаких расуждений я не нашёл, то откуда появилась конечная формула не совсем ясно.
Хотя, на самом деле, это ведь O-символика и я точно так же мог бы написать O(n^0.1), что тоже было бы правильно. Поэтому тут всё неоднозначно.
Последнее. Товарищ lime ссылается на неких авторов, которые смогли найти алгоритм со сложностью O(n^1,5). Могу совершенно точно сказать, что самый вычислительно сложный метод "метод половинного деления" имеет сложность O(n^0.5)
А вот О. Н. Василенко в книге "Теоретико-числовые алгоритмы в криптографии" говорит, что алгоритмов факторизации, которые имеют более высокие показатели, чем с субэкспоненциальной сложностью в данный момент не существует. И пока я не видел ниодного алгоритма, который бы это опровергнул.
Одним словом - смысл статьи я не уловил. Да и вообще, имхо, нельзя говорить о сложности решения какой-то задачи, что пытается сделать автор. Можно говорить лишь о сложности вычисления какого-то алгоритма.
|
| |
Во-первых, если Вы что-то знаете о факторизации, но ничего... 03.12.04 08:03
Автор: lime Статус: Незарегистрированный пользователь
|
> Во-первых, совершенно неясно как помогает представленная
> форма сведения факторизовать произвольное n.
Во-первых, если Вы что-то знаете о факторизации, но ничего не слышали о проблеме NP-полноты или слышали но, как следует из неправильного употребления Вами некоторых терминов, недостаточно для подобного ответа, то следует перечитать написанное еще как минимум раз десять.
Разве где то было упомянуто, что данное представление помогает факторизовать число?
Если рассказывать всю историю сначала, то основанием для данного материала (потому что это скорее методический материал, а не статья) послужило данной обсуждение http://www.bugtraq.ru/cgi-bin/forum.mcgi?type=sb&b=15&m=111593
Задачей было показать полиномиальное сведение задачи ФАКТОРИЗАЦИЯ к одной из NP-полных задач (надеюсь, знаете зачем это обычно делается).
Материал этот не готовился для FAQ, я просто попросил администратора разместить его где-нибудь. Он счел нужным поместить его в FAQ и только.
> Во-вторых, в статье я нигде не нашёл, откуда следует, что
> сложность будет именно O(n^2), а не как-то по-другому.
Верно. Его нигде нет, т.к. задачей было на примере показать методику сведения. Операции умножения в столбик учат в первом классе и порядок сложности легко считается (по крайней мере у людей, для которых данный материал изначально был предназначен, никаких вопросов не возникло).
> Вообще написано достаточно пространно и если я правильно
> понял статью, то автором предлагается свести конкретное
> число к логическому высказыванию, откуда найти сомножители.
К терминологии. Исходная формула задачи ВЫП - это не логическое высказывание, если говорить строго.
> Хотя это я уже сам домыслил (а по-другому вообще непонятно
> как факторизировать, опираясь на приведённый текст).
> Однако, если следуя подобным рассуждениям попытаться
> прописать термы для числа длиной по-больше, то вообще
> делается видно, что количество переменных и логических
> переменных возрастает гораздо быстрее, чем функция x^2. Т.
> к. для факторизации никаких расуждений я не нашёл, то
> откуда появилась конечная формула не совсем ясно.
Внизу приведена табличка из которой очень хорошо виден рост сложности задачи по мере роста размера входных данных и очень замечательно видно, что рост как раз таки не превышает x^2. Квадрат - это верхняя ассимптотическая граница. Хотя, возможно, в порыве порицания Вы просто не дочитали материал до конца и бросились писать гневный отзыв. :)
> Хотя, на самом деле, это ведь O-символика и я точно так же
> мог бы написать O(n^0.1), что тоже было бы правильно.
> Поэтому тут всё неоднозначно.
Без комментариев (потому что даже не понял смысла).
> Последнее. Товарищ lime ссылается на неких авторов, которые
> смогли найти алгоритм со сложностью O(n^1,5). Могу
> совершенно точно сказать, что самый вычислительно
> сложный метод "метод половинного деления" имеет
> сложность O(n^0.5)
Да вообще то любой ВНИМАТЕЛЬНО прочитавший ВСЁ, что я написал, понял, что сложность полученной задачи ВЫП зависит исключительно от того, какой метод умножения мы используем. Задачей было - показать пример сведения на основе правил умножения, с которыми знаком каждый из тех, кто посещает этот форум. Имеется ввиду умножение столбиком.
> А вот О. Н. Василенко в книге "Теоретико-числовые алгоритмы
> в криптографии" говорит, что алгоритмов факторизации,
> которые имеют более высокие показатели, чем с
> субэкспоненциальной сложностью в данный момент не
> существует. И пока я не видел ниодного алгоритма, который
> бы это опровергнул.
А я вроде и не утверждаю, что создал его.
> Одним словом - смысл статьи я не уловил. Да и вообще, имхо,
> нельзя говорить о сложности решения какой-то задачи, что
> пытается сделать автор. Можно говорить лишь о сложности
> вычисления какого-то алгоритма.
Опять же повторюсь, но до конца дочитывать надо.
Последний небольшой раздельчик с заголовком "Сложность". О сложности было упомянуто только там.
Так вот термин "сложность" там применяется притяжательно к термину "алгоритм". Так что опять у меня непонятки.
|
| | |
Ответ (долгожданный) 28.12.04 18:03
Автор: Heller <Heller> Статус: Elderman
|
Признаю, с NP-полнотой я знаком лишь поверхностно и критика моя была обращена больше не в адрес статьи, а в адрес заключения, где приводились сведения о сложности факторизации. Насколько я понял вначале, смысл всей статьи к этому и сводился - так уж построено изложение. Обычно все выводы пишутся в конце, а там как раз сложность факторизации - а по данному вопросу в статье ничего конкретного не наблюдается.
Далее, вы говорите, что асимптотика видна из таблицы. Не согласен категорически - из таблицы не видноничего Это то же самое что строить график синуса в точках pi*n и утверждать, что данная функция константа.
По поводу ассимтотики. Если разобраться, то "сложность=O(x^2)" означает ни что иное, как "сложность возрастает при возратании x быстрее чем функция x^2 (в пределе, понятно)". Однако т. к. сложность возрастает быстрее чем x^2, то она естесственно будет возрастать быстрее чем x^0.5 - поэтому можно написать O(x^0.5) и формально это так же будет верно. Задача нахождения сложности таким образом сводится к нахождению самой быстрорастущей функции, которая растёт тем не менее медленнее, чем сложность. Ничего похожего на подобные рассуждения я в статье не увидел (опять же обращаю внимание, что статья построена таким образом, что складывается впечатление, что вся её цель - показать сложность факторизации).
Вот, вроде как на основные вопросы высказался. Итог - статью объективно оценить я не в состоянии, а вот за Литературный талант двойку :-) Сама организация статьи наталкивает на мысли о факторизации - она написана таким образом, что сложность факторизации кажется всей целью, а, как видно из Вашего ответа, это не совсем так.
Ещё хочу извиниться за столь позний ответ - работы куча, а что бы писать о математике требуется время. Поэтому не отвечал.
|
| | | |
Насколько я понимаю в классах сложности, NP-полные задачи... 29.12.04 13:11
Автор: amirul <Serge> Статус: The Elderman
|
> Признаю, с NP-полнотой я знаком лишь поверхностно и критика
> моя была обращена больше не в адрес статьи, а в адрес
> заключения, где приводились сведения о сложности
> факторизации. Насколько я понял вначале, смысл всей статьи
> к этому и сводился - так уж построено изложение. Обычно все
> выводы пишутся в конце, а там как раз сложность
> факторизации - а по данному вопросу в статье ничего
> конкретного не наблюдается.
Насколько я понимаю в классах сложности, NP-полные задачи это такие NP задачи, решение хотя бы одной из которых за полиномиальное время автоматически приводит к решению ВСЕХ NP-полных задач за полиномиальное же время. Чаще всего для доказательства NP-полноты задачи сводят к задаче выполнимости. Если сведение возможно за полиномиальное время (которое тоже следует включить в оценку сложности), то задача - NP-полная.
> Далее, вы говорите, что асимптотика видна из таблицы. Не
> согласен категорически - из таблицы не видноничего Это
> то же самое что строить график синуса в точках pi*n и
> утверждать, что данная функция константа.
> По поводу ассимтотики. Если разобраться, то
> "сложность=O(x^2)" означает ни что иное, как "сложность
> возрастает при возратании x быстрее чем функция x^2 (в
Нет. O-нотация говорит о том, что возрастание функции в пределе РАВНО возрастанию того, что в скобках у O.
То бишь если говорить что f(x) = O(g(x)), то
limit(x = infinity, f(x) / g(x)) = 1;
> пределе, понятно)". Однако т. к. сложность возрастает
> быстрее чем x^2, то она естесственно будет возрастать
> быстрее чем x^0.5 - поэтому можно написать O(x^0.5) и
Неправильно. limit(x = infinity, (x ^ 2) / (x^0.5)) = infinity, а не 1. Следовательно говорить об эквивалентности O(x^2) и O(x^0.5) не следует
> формально это так же будет верно. Задача нахождения
> сложности таким образом сводится к нахождению самой
> быстрорастущей функции, которая растёт тем не менее
> медленнее, чем сложность. Ничего похожего на подобные
Исходя из неправильного понимания O-нотации это утверждение неверно.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
