Доказать NP-полноту задачи о функциях k-значной логики

romanenkoroman1

Есть схема функциональных элементов. Функциональные элементы - все функции k-значной логики с числом переменных от 1 до n. Нужно проверить, что реализуемая схемой функция устойчива, т.е.
max|xi-yi|<=A => |F(x1....xN)-F(y1....yN)|<=A
либо (более сильное свойство)
|F(x1....xN)-F(y1....yN)|<=max |xi-yi|

romanenkoroman1

не из основного курса задачка, но нужна. Похоже, что NP-полна, но как-то не получается доказать. Кто-нибудь что-нибудь подсказать может?

Lokomotiv59

Кажись можно доказать NP-полноту сопряженной задачи — проверку неустойчивости функции, соответствующей схеме (если это интересует — могу написать). Че делать с этой задачей — хз.
Вообще как ты себе представляешь сертификат, проверяющий правильность решения твоей задачи ? Это к вопросу о том, почему она вообще принадлежит классу NP.

romanenkoroman1

а, это верно. coNP - это тоже хорошо

Lokomotiv59

Ну вот че я придумал для co-задачи.
Сводим к решению задачи о выполнимости булевой СФЭ.
Пусть f(x, y, ...) — булева функция от булевых переменных x, y, ...
Построим функцию k-значной логики f'(x', y', ...):
f'(x', y', ...) := (k-1) * f(Pr(x' Pr(y' ...
где Pr(z')=(z' > 0 ? 1 : 0).
Рассмотрим произвольную булеву СФЭ, реализуемая функция которой отлична от тождественной 1.
Пусть например, она имеет вид f(g(x, y h(y, z. Надо построить СФЭ элементов k-значной логики
такую, что она будет неустойчива тогда и только тогда, когда данная схема выполнима.
Рассмотрим k-значную СФЭ: f'(g'(x', y' h'(y', z'.
Если булева схема выполнима, и отлична от тождественной 1, то есть набор
* x_0, y_0, z_0, на котором СФЭ равна 0 и набор
* x_1, y_1, z_1, на котором СФЭ равна 1.
Тогда k-значная СФЭ на первом наборе будет равна 0, а на втором — (k-1).
При этом, $|x_0-x_1|, |y_0-y_1|, |z_0-z_1| <= 1$, то есть k-значная СФЭ
неустойчива.
С другой стороны, пусть булева схема на всех наборах равна 0.
Тогда k-значная СФЭ тоже на всех наборах равна нулю: если бы нашелся набор
(x', y', z' на котором k-значная СФЭ больше 0, то булева СФЭ
была бы равна 1 на наборе (Pr(x' Pr(y' Pr(z'.
Все правильно?

romanenkoroman1

вроде правильно, спасибо. можно сказать, что мы свели к этой задаче проверку булевой функции на "неконстантность", что тоже явно NP-полно, чтоб не писать "пусть она выполнима, но не тождественная 1"
А как насчёт случая, когда схема имеет вид дерева? Вроде NP-полнота сохранится, т.к. "Выполнимость" и для формул NP-полна. Правильно? А то я уж всё позабыл

Lokomotiv59

А как насчёт случая, когда схема имеет вид дерева? Вроде NP-полнота сохранится, т.к. "Выполнимость" и для формул NP-полна. Правильно? А то я уж всё позабыл
Правильно. Собственно формулы использовались только для удобства записи.
Кстати, мне тут показалось, что если задача L — NP-полна и P != NP, то про сопряженную задачу L'
можно сказать, что она не решается за полиномиальное время, независимо от того, принадлежит L'
классу NP или нет.

romanenkoroman1

Решить - это в случаях любого ответа? И "ДА и "НЕТ"? Если так, то очевидно, ведь коль мы можем решить задачу за полиномиальное время без подсказки, то и с подсказкой как-нибудь решим.
А вообще, принадлежность NP - это ведь "положительное" свойство, т.е. если оно не выполняется, то всё только хуже
Надо классиков почитать, может, у них что-нить есть
А кстати, есть хоть одна задача, принадлежащая и NP и сoNP одновременно?

Lokomotiv59

Да, например класс P=coP.

romanenkoroman1

ну а кроме?
скажем так: из задач, про которые не доказано, что они из Р?

Lokomotiv59

Для NP-полных задач это равносильно исследованию соотношения множеств NP и co-NP — то есть нерешенная задача. А других NP-задач не из P я не знаю ;)
А вообще ты задаешь вопросы на миллион долларов :grin:

romanenkoroman1

Меньшими категориями я и не мыслю :)
А ведь в случае P!=NP есть же задачи, которые не решаются полиномиально, но при этом не NP-полны. Вот если на такую наткнуться, то это трындец: и быстрый алгоритм не найти, и NP-полноту не доказать

Xephon

А ведь в случае P!=NP есть же задачи, которые не решаются полиномиально, но при этом не NP-полны.

Ты умеешь это доказывать?

natunchik

Факторизация, например?
Она в BQP (а, значит, не в NP, если P!=NP но вроде не в P.

Lokomotiv59

Кстати, в качестве офтопа:
есть ли алгоритмы шифрования с открытым ключом, основанные на известном решении NP-полной задачи,
ну скажем, задачи коммивояжера? :grin:

Xephon

По этому поводу есть теорема Лэднера:
"http://en.wikipedia.org/wiki/Ladner's_theorem"
А вот если ты докажешь, что факторизация является такой задачей, то всем будет интересно, думаю.

romanenkoroman1

Нам вроде рассказывали про протокол шифрования, основанный на задаче о рюкзаке. Мало что про него помню
Оставить комментарий
Имя или ник:
Комментарий: