Пусть А сводится к B, т.е. . Таким образом, машина Тьюринга приема имеет доступ к оракулу для . Пусть машина Тьюринга, принимающая будет а оракул для будет . Типы скидок:
Сокращение Тьюринга: может сделать несколько запросов к .
Уменьшение Карпа: также называется «сокращением по Тьюрингу за полиномиальное время»: входные данные для должны быть построены за время полимеризации. Более того, количество запросов к должно быть ограничено полиномом. В этом случае: .
Много-одно сокращение Тьюринга: может сделать только один запрос к во время его последнего шага. Следовательно, ответ оракула не может быть изменен. Однако время, необходимое для построения входа в не обязательно должно быть ограничено полиномом. Эквивалентно: ( обозначает сокращение много-один)
, если вычислимая функция такая , что .
Сокращение Кука: также называется «сокращением много-одного полиномиального времени»: сокращение много-одного, где время, необходимое для создания входа в должно быть ограничено полиномом. Эквивалентно: ( обозначает сокращение много-один) ≤ p m
, если ∃ вполи-временивычислимая функция F : Е * → Е * такойчто F ( х ) ∈ B .
Парсимонное сокращение: Также называется « за полиномиальное время один-один сокращение»: сокращение Повара , где каждый экземпляр сопоставляется с уникальным экземпляром B . Эквивалентно: ( ≤ p 1 обозначает экономное сокращение)
, если ∃ вполи-времявычислимы биекции е : Е * → Е * такойчто F ( х ) ∈ B .
Эти сокращения сохраняют количество решений. Следовательно .
Мы можем определить больше типов сокращений, ограничив количество запросов оракула, но не обращая на них внимания, может кто-нибудь любезно сказать мне, правильно ли я получил номенклатуру для различных используемых типов сокращений. Определены ли NP-полные проблемы относительно сокращения Кука или экономного сокращения? Может ли кто-нибудь любезно привести пример проблемы, которая является NP-полной под Cook, а не под экономным сокращением.
Если я не ошибаюсь, класс # P-Complete определяется относительно сокращений Карпа.
источник
источник