Типы сокращений и соответствующие определения твердости

15

Пусть А сводится к B, т.е. . Таким образом, машина Тьюринга приема имеет доступ к оракулу для . Пусть машина Тьюринга, принимающая будет а оракул для будет . Типы скидок:AВAВAMAВОВ

  • Сокращение Тьюринга: может сделать несколько запросов к .MAОВ

  • Уменьшение Карпа: также называется «сокращением по Тьюрингу за полиномиальное время»: входные данные для должны быть построены за время полимеризации. Более того, количество запросов к должно быть ограничено полиномом. В этом случае: .ОВOBPA=PB

  • Много-одно сокращение Тьюринга: может сделать только один запрос к во время его последнего шага. Следовательно, ответ оракула не может быть изменен. Однако время, необходимое для построения входа в не обязательно должно быть ограничено полиномом. Эквивалентно: ( обозначает сокращение много-один)MAOBOBm

    AmB , если вычислимая функция такая , что .f:ΣΣf(x)BxA

  • Сокращение Кука: также называется «сокращением много-одного полиномиального времени»: сокращение много-одного, где время, необходимое для создания входа в должно быть ограничено полиномом. Эквивалентно: ( обозначает сокращение много-один)p mOBmp

    , если вполи-временивычислимая функция F : Е *Е * такойчто F ( х ) BAmpBf:ΣΣ .f(x)BxA

  • Парсимонное сокращение: Также называется « за полиномиальное время один-один сокращение»: сокращение Повара , где каждый экземпляр сопоставляется с уникальным экземпляром B . Эквивалентно: ( p 1 обозначает экономное сокращение)AB1p

    , если вполи-времявычислимы биекции е : Е *Е * такойчто F ( х ) BA1pBе:Σ*Σ* .е(Икс)ВИксA

    Эти сокращения сохраняют количество решений. Следовательно .#MAзнак равно#ОВ

Мы можем определить больше типов сокращений, ограничив количество запросов оракула, но не обращая на них внимания, может кто-нибудь любезно сказать мне, правильно ли я получил номенклатуру для различных используемых типов сокращений. Определены ли NP-полные проблемы относительно сокращения Кука или экономного сокращения? Может ли кто-нибудь любезно привести пример проблемы, которая является NP-полной под Cook, а не под экономным сокращением.

Если я не ошибаюсь, класс # P-Complete определяется относительно сокращений Карпа.

Павитран Айер
источник

Ответы:

7

Ваше определение экономных сокращений неверно. Вы путаете это с одночленным сокращением за полиномиальное время, что является частным случаем сокращений Карпа. Они не сохраняют количество «решений». Пожалуйста, смотрите этот ответ для получения дополнительной информации о сокращениях с учетом количества сертификатов.

В остальном все в порядке, хотя обычно их лучше просматривать на двухмерной диаграмме:

  • сложность редукции: вычислимое, полиномиальное время, логарифмическое пространство и т. д.
  • тип доступа: тьюринг, много-один, один-один и т. д.

Определены ли NP-полные проблемы относительно сокращения Кука или экономного сокращения?

Твердость и полнота N P определяются по сокращению Карпа (polytime много-один), а не по Кука или экономному сокращению.Nп

Может ли кто-нибудь любезно привести пример проблемы, которая является NP-полной под Cook, а не под экономным сокращением.

Возьмите дополнение SAT, оно завершено для при сокращениях Кука, оно не считается полным для N P при сокращениях Карпа. Сокращения в Карпе включают в себя уменьшение времени один-на-один.NпNп

класс # P-Complete определен относительно сокращений Карпа

Обратите внимание, что #п - это не класс задач решения, это класс задач вычисления функций. Его твердость и полнота обычно определяются при сокращениях Кука (полимеризация по Тьюрингу). См., Например, Арора и Барак, стр. 346.

Кава
источник
Извините, я, кажется, поменял терминологию "уменьшение Карпа" и "сокращение Кука". Если я обменяю это, то это соответствует вашим ответам. Благодарю. Что касается экономных сокращений, вы говорите, что они не сохраняют количество «решений»? Если это так, я вижу в теореме 17.10 Ароры и Барака (стр. 299), что экономные сокращения действительно сохраняют число решений. Другая ссылка: ( cse.cuhk.edu.hk/~andrejb/csc5170/notes/10L10.pdf )
Павитран Айер
Здесь говорится об экономном сокращении с L до SAT, отображает каждый экземпляр x в L на уникальный экземпляр SAT (то есть, карта сокращения - один-один): [ cse.cuhk.edu.hk/~andrejb/csc5170/notes /10L10.pdf] . Разве не правильно предполагать, что если число решений сохраняется за счет сокращения, то карта является единичной?
Павитран Айер
@Pavithran, то, что вы написали в своем вопросе, не было определением экономных сокращений. Ответ можно найти в упражнении 2.13 в их книге.
Каве
0

ОВ

Бьорн Линдквист
источник
В частности, определения сокращений Кука и Карпа были изменены.
Дэвид Ричерби