Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/NTIME-NlogN-reduction-3SAT

Ссылки сюда (4) →

Покажите, что для любого языка , можно построить полиномиальную Карп-сводимость, от слов длины n, к 3SAT-формулам длины .

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.