Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Вы уверены, что ошибки действительно есть? 17.02.05 19:06 Число просмотров: 3384
Автор: Партизан Статус: Незарегистрированный пользователь
|
> > > > А не пытались ли Вы найти ошибку в
> доказательстве
> > у
> > > > Тельпиза? Хотя бы в той статье про 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 раз.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
