Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/NTIME-NlogN-reduction-3SAT — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: «Покажите, что для любого языка <m>L \in NTIME(T(n))</m>, можно построить полиномиальную Карп-своди…») |
(нет различий)
|
Версия 18:16, 29 мая 2014
Покажите, что для любого языка , можно построить полиномиальную Карп-сводимость, от слов длины n, к 3SAT-формулам длины .