Не могу понять смысл фразы :)

[Чудо-в-перьях]

Читаю работу Рыбакова М.Н. "Сложность константного фрагмента пропозициональной динамической логики" (нужно для моей деятельности :)) и не могу понять вот такое высказывание:
"Так, проблема выполнимости булевых формул $NP$-
полна [6], а проблема выполнимости булевых формул от n переменных полиноми-
ально разрешима при любом фиксированном $ n $: в качестве полиномиального алго-
ритма, решающего эту проблему, можно взять алгоритм, основанный на постро-
ении таблиц истинности фиксированного размера  состоящих из $2^n$ строк."

так вот, почему алгоритм, базирующийся на построении таблиц истинности и для каждого набора $n$ -ного числа переменных выдающий таблицу размером $2^n$ строк, является полиномиальным?!.. разве здесь не экспоненциальная сложность- $O(2^{poly(n)})$?
При $n = 10$ в таблице будет $1024$ строчки. Попробовал бы кто-нибудь на практике построить такую табличку)))

[mkot]

А количество ли переменных является размером входа?

[Xaositect]

Сложность измеряется как функция от длины формулы.
А $n$ фиксировано, поэтому $2^n$ - это просто некоторая константа.

[Чудо-в-перьях]

Xaositect в сообщении #377178 писал(а):

Сложность измеряется как функция от длины формулы.
А $n$ фиксировано, поэтому $2^n$ - это просто некоторая константа.

Спасибо!.. Теперь,кажется, поняла.

Но все равно не могу понять такой момент: практически во всех логических системах, где алгоритм разрешимости исследуется на сложность, размер формулы, истинность или ложность (общезначимость/необщезначимость) которой устанавливается, длина формулы в каждом конкретном случае фиксирована и не меняется -- в тех же модальных логиках и т.п. Но метод проверки нередко оказывается там и $EXPTIME$ - трудным, и $EXPTIME$ - полным, и т.п.

И все равно чисто практически вычисление константы $2^n$ от достаточно большого $n$ при построении таблиц истинности -- не самая простая задача, говорю как преподаватель а уж про $3^n$ (при работе с трехзначными логиками) я вообще молчу )). Т.е. когда мы с этими логиками табличным образом работаем, мы в худшем случае должны рассмотреть все $k^n$ наборов. Почему этот процесс будет полиномиальным?

mkot в сообщении #377117 писал(а):

А количество ли переменных является размером входа?

А почему в данном случае -- в случае вычисления размера таблицы (а не истинности\ложности формулы) --количество переменных нельзя рассматривать как размер входа?
Т.е. я хотела сказать, что процесс построения самой таблицы д.б. экспоненциальным от числа переменных.
а уже подсчет значения формулы -- от длины всей формулы целиком.


-- Сб ноя 20, 2010 14:08:30 --

Xaositect
Все, поняла
"Математически есть смысл рассматривать лишь бесконечные последовательности задач: если размер входа ограничен, всякий алгоритм можно заменить большущей, но все же константного размера таблицей, в которой будет записано соответствие между входами и выходами, и алгоритм будет иметь константную сложность (и совершенно не важно, что константа эта может оказаться больше числа атомов во Вселенной)"
Я непростительно перепутала практический и теоретический аспекты))

[Чудо-в-перьях]

Так какой мы вывод сделаем из всего этого?))

[Xaositect]

Чудо-в-перьях в сообщении #378453 писал(а):

Так какой мы вывод сделаем из всего этого?))

Для каждого фиксированного $n$ алгоритм полиномиальный, но мультипликативная константа очень быстро растет с ростом $n$

[Чудо-в-перьях]

Полностью согласна!...))) Большое спасибо за помощь!..:)

Следовательно, на практике подобные алгоритмы также являются плохоприменимыми, только для данных небольшого размера они подходят