Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Вот именно, что внимателней 09.03.05 13:08 Число просмотров: 3297
Автор: 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, но все равно значительная чать переменных, мы полимиальной сложности не получим.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
