РЕДАКТИРОВАТЬ в 2011/02/08: После того, как некоторые ссылки были найдены и прочитаны, я решил разделить оригинальный вопрос на два отдельных. Вот часть, касающаяся UP vs NP, для части синтаксических и семантических классов см. Преимущества для синтаксических и семантических классов .
(однозначное полиномиальное время, см. вики и зоопарк для ссылок) определяется как языки, определяемые -машинами с дополнительным ограничением, которое
- На любом входе есть не более одного приемлемого пути вычисления.
Точные отношения между vs и vs остаются открытыми. Мы знаем, что однонаправленные функции в худшем случае существуют тогда и только тогда, когда , и существуют оракулы относительно всех возможностей включений .U P U P N P P ≠ U P P ⊆ U P ⊆ N P
Меня интересует, почему vs является важным вопросом. Люди склонны верить (по крайней мере, в литературе ), что эти два класса разные, и моя проблема заключается в следующем:N P
Если , произошли ли "плохие" последствия?
В 2003 году в блоге, посвященном сложности, есть соответствующий пост . И если я правильно понимаю, результаты Хемаспандры, Найка, Огивары и Сельмана показывают, что если
- Существует язык такое , что для каждой выполнимой формулы есть уникальное удовлетворяющее задание с в , L ϕ( ϕ , x ) L
затем полиномиальная иерархия разрушается до второго уровня. Такое утверждение не известно, если выполняется .
источник
Ответы:
Известно, что подразумевает поскольку Коблер, Шонинг и Торан доказали, что тогда и только тогда, когда , Легко видеть, что содержится в .S p a n P = # P U P = N P S p a n P = # P # P S p a n PUP=NP SpanP=#P UP=NP SpanP=#P #P SpanP
Функция находится в если есть машинный преобразователь Тьюринга такой, что для всех , - это число отдельных выходов на вход . xf:Σ∗→N N P M x f ( x )SpanP NP M x f(x) M x
Дж. Коблер, У. Шонинг и Дж. Торан. О подсчете и приближении , Acta Informatica, 26: 363-379, 1989.
источник