Последствия UP равняются NP

19

РЕДАКТИРОВАТЬ в 2011/02/08: После того, как некоторые ссылки были найдены и прочитаны, я решил разделить оригинальный вопрос на два отдельных. Вот часть, касающаяся UP vs NP, для части синтаксических и семантических классов см. Преимущества для синтаксических и семантических классов .


UP (однозначное полиномиальное время, см. вики и зоопарк для ссылок) определяется как языки, определяемые -машинами с дополнительным ограничением, котороеNP

  • На любом входе есть не более одного приемлемого пути вычисления.

Точные отношения между vs и vs остаются открытыми. Мы знаем, что однонаправленные функции в худшем случае существуют тогда и только тогда, когда , и существуют оракулы относительно всех возможностей включений .U P U P N P PU P PU PN PPUPUPNPPUPPUPNP

Меня интересует, почему vs является важным вопросом. Люди склонны верить (по крайней мере, в литературе ), что эти два класса разные, и моя проблема заключается в следующем:N PUPNP

Если , произошли ли "плохие" последствия?UP=NP

В 2003 году в блоге, посвященном сложности, есть соответствующий пост . И если я правильно понимаю, результаты Хемаспандры, Найка, Огивары и Сельмана показывают, что если

  • Существует язык такое , что для каждой выполнимой формулы есть уникальное удовлетворяющее задание с в , L ϕNPLϕ( ϕ , x ) Lx(ϕ,x)L

затем полиномиальная иерархия разрушается до второго уровня. Такое утверждение не известно, если выполняется .UP=NP

Сянь-Чжи Чан 張顯 之
источник
(1) Легко увидеть (почти по определению), что UP и BPP имеют полные проблемы, если «проблемы» могут относиться к обещанным проблемам. Они, как известно, не имеют полных языков . (2) Я не знаю точного определения синтаксических классов. Является ли PH синтаксическим? У него нет полной проблемы (даже с обещанием), если не разрушится полиномиальная иерархия. (3) Я не знаю, как вы используете обозначение «PromiseUP». Если NP означает класс языков, распознаваемых машиной NP, а PromiseUP означает класс проблем с обещаниями, распознаваемых машиной UP, то, очевидно, они не могут быть равными.
Цуёси Ито
@Tsuyoshi: Спасибо за вопросы. (1) Под проблемами я подразумеваю языки , я виноват в том, что не пишу это ясно. (2) Мы определяем синтаксические классы как имеющие листовые языковые характеристики на машинах с многопоточностью. PH является особенным, так как не известна листовая языковая характеристика по многим временам, где гарантированы естественные полные языки; но у PH действительно есть характеристика языка листа пространства журнала . (подробнее)
Сянь-Чжи Чанг 之 之
(продолжение) (3) Возможно, использование PromiseUP не правильно. Здесь под PromiseUP я подразумеваю класс языков , такой, что для экземпляров yes у ​​машины есть уникальный принимающий путь, и ни для каких случаев у машины нет нуля или хотя бы два принимающих пути.
Сянь-Чи Чанг 之 之
Спасибо за ответ. Что касается (3), то из беглого взгляда на статью Хемаспандры, Найка, Огихары и Сельмана я не могу найти способ сформулировать результат с точки зрения решения проблем. Кстати, ссылка на статью не работает. Вот ссылка на версию журнала .
Цуёси Ито
2
Просто чтобы убедиться, PromiseUP полностью отличается от того, что вы описали. Как я уже писал, PromiseUP - это версия проблемы с обещаниями UP; то есть это класс проблем обещаний, имеющих недетерминированную машину М Тьюринга за полиномиальное время, такую, что для экземпляров «да» M имеет ровно один принимающий путь, а для без экземпляров M не имеет принимающих путей. Хотя я считаю, что PromiseUP является традиционным названием для этого класса, некоторые люди (включая меня) пишут этот класс просто как UP.
Цуёси Ито

Ответы:

4

Известно, что подразумевает поскольку Коблер, Шонинг и Торан доказали, что тогда и только тогда, когда , Легко видеть, что содержится в .S p a n P = # P U P = N P S p a n P = # P # P S p a n PUP=NPSpanP=#PUP=NPSpanP=#P#PSpanP

Функция находится в если есть машинный преобразователь Тьюринга такой, что для всех , - это число отдельных выходов на вход . xf:ΣNN P M x f ( x )SpanPNPMxf(x)Mx

Дж. Коблер, У. Шонинг и Дж. Торан. О подсчете и приближении , Acta Informatica, 26: 363-379, 1989.

Мухаммед Аль-Туркистани
источник
2
Этот ответ ( cstheory.stackexchange.com/a/20645/495 ) также работает здесь, так как если то гипотеза о непересекающихся парах ложна. N PUP=NPNP
Мухаммед Аль-Туркистани