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

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

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

Задача зарезервирована: Nikitashapovalov 00:04, 20 декабря 2024 (UTC)

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

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

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