Интуиция для класса UP

Класс UP определяется так:

Класс решения задач, решаемых машиной NP, такой, что

Если ответ «да», принимается ровно один путь вычислений.

Если ответ «нет», все пути вычислений отклоняются.

Я пытаюсь развить интуицию для этого определения.

Можно ли сказать, что проблемы UP - это проблемы с уникальными решениями (например, первичная факторизация)?

Это кажется мне близким к истине; но я не могу не думать , что это означало бы, так как UP содержит Р и содержится в NP, что в случае , если P = NPмы получим , что P = UP = NP, таким образом , все проблемы NPимеют уникальные решения , как хорошо, что кажется , как - то доказуемо не так: P != NPпо сокращение до абсурда. Я надеюсь, что в этом параграфе не слишком много догадок и взмахов рук на ваш вкус.

cc.complexity-theory complexity-classes Валя
источник

Определение «уникального решения» проблематично: например, решение игр с проверкой четности находится в UP ( на самом деле UP coUP), но может быть много выигрышных стратегий. Уникальный свидетель более вовлечен.

\cap

$\cap$

Шаул

хм, так что это означало бы, что есть алгоритм для недетерминированной машины Тьюринга, который не является «недетерминированным испытанием каждого решения» (я думал, что это идея в основе эквивалентности определений NP для n.-d. и т. д.), но что-то более сложное, всегда приводящее к уникальному результату из многих возможных ... Это правильно? Есть ли другой способ сформулировать это, например, используя только идею детерминированного Tm (можно определить NP, используя только его)?

валя

Интуиция уникального свидетеля верна, но ее следует использовать осторожно, поскольку это не означает, что каждый NTM для нее имеет уникальный прогон.

Шаул

Мне нравится этот вопрос! У меня была точно такая же путаница, но я не видел умного способа перевести эту путаницу в простое доказательство того, что P! = NP. Отлично сработано!

Винсент

Кстати, ваш вопрос из вашего последнего комментария с тех пор получил ответ на странице Википедии для класса UP

Винсент

Ответы:

Ваша путаница, по-видимому, связана с тем, что проблемы имеют более одного способа определения «решения» (или свидетеля). Тип решения не является частью определения проблемы. Например, для раскраски графа очевидным типом решения является назначение одного цвета для каждой вершины (используя самое большее необходимое количество цветов); однако по теореме Галлая – Хассе – Роя – Витавера $\mathsf{NP}$ Другой тип решения, который одинаково хорошо работает, - это присвоение ориентации каждому ребру (создание направленных путей не более необходимого количества вершин). Эти два типа решений могут быть проверены за полиномиальное время, но с помощью разных алгоритмов, и они также имеют разные комбинаторные свойства. Например, для типичного экземпляра задачи количество назначений цвета вершины будет отличаться от количества ориентаций ребер. Многие исследования по ускорению экспоненциальных алгоритмов для задач типа NP могут быть истолкованы как поиск нового семейства решений той же проблемы, которое имеет меньше возможностей для проверки.

Каждая проблема в имеет «решение», состоящее только из пустой строки. Чтобы убедиться, что это решение, просто убедитесь, что строка решения пуста, а затем запустите алгоритм полиномиального времени для экземпляра задачи. При таком типе решения каждый экземпляр yes имеет ровно одно действительное решение, а каждый экземпляр no имеет ноль, что соответствует определению и показывает, что . Если то такое же решение с пустой строкой также будет работать для каждой задачи в , показывая, что $\mathsf{P}$ $\mathsf{NP}$ $\mathsf{UP}$ $\mathsf{P}\subset\mathsf{UP}$ $\mathsf{P}=\mathsf{NP}$ $\mathsf{NP}$ $\mathsf{NP}=\mathsf{UP}$ , Таким образом, нет никакого противоречия между фактом, что решение с пустой строкой является уникальным, и фактом, что некоторый другой тип решения для той же самой проблемы не является уникальным.

Дэвид Эппштейн
источник

Значит, значение не противоречиво? Следующая задача является NP-полной. Для данного N есть ли коэффициент N в данном диапазоне скажем, где и ? В этом диапазоне может быть более одного фактора, и решение может быть не уникальным?

U P = N P

$UP=NP$

[a, b]

$[a,b]$

a, b \sim N^{\frac{1}{4}}

$a,b\sim N^{\frac{1}{4}}$

a < b

$a<b$

T ....

Опять же, вы ошибочно полагаете, что решение может быть только тем фактором, который вы ищете. Могут быть и другие способы решения той же проблемы (например, получение ответа «да» или «нет» для заданного N), которые не состоят из фактора. И если P = NP, то пустая строка соответствует техническим требованиям решения NP - вы можете проверить это за полиномиальное время - и это действительно не фактор, а решение той же проблемы.

Дэвид Эппштейн

Этот ответ абсолютно блестящий, поскольку учит нас даже больше, чем просят!

Винсент

Я согласен с комментарием Шолля, что интуиция наличия уникального свидетеля верна, но неуловима. Аргумент в вашем последнем абзаце может быть сделан технически точным и подчеркивает тонкость против . В частности, проблема в вашем последнем абзаце, по сути, заключается в том, : $\mathsf{UP}$ $\mathsf{NP}$ $\mathsf{NPMV} \subseteq_{c} \mathsf{NPSV}$

$\mathsf{NPMV}$ - это класс частичных многозначных функций, вычисляемых в недетерминированный полиномиальный момент времени, то есть каждая принимающая недетерминированная ветвь получает выходное значение (если на каком-либо входе нет принимающих путей, то нет выходных данных , что приводит к тому, что они должны быть только частичными функциями). Это тесно связано с поисковой версией проблем . $\mathsf{NP}$

$\mathsf{NPSV}$ - это класс однозначных функций в , то есть могут принимать несколько ветвей, но если какие-либо ветви принимают, все принимающие ветви должны выводить одно и то же значение. $\mathsf{NPMV}$

Интуитивно понятно, что ваш последний абзац говорит о том, всегда ли вы можете выбрать из числа свидетелей для данного верификатора какой-либо проблемы одного свидетеля. Это вопрос о том, является ли каждый имеет функцию к уточнение (обозначается ). Если это так, то полиномиальная иерархия разрушается (см. Hemaspaandra, Naik, Ogihara и Selman «Вычисление решений однозначно разрушает полиномиальную иерархию » ). $\mathsf{NP}$ $\mathsf{NPMV}$ $\mathsf{NPSV}$ $\mathsf{NPMV} \subseteq_{c} \mathsf{NPSV}$

В отличие от , не известно, что такое следствие следует из . По сути, потому что, учитывая язык , (свидетели a) машины для не должны иметь ничего общего с (свидетелями любого) другого компьютера (ов) ) для . $\mathsf{UP}$ $\mathsf{NP} = \mathsf{UP}$ $L \in \mathsf{NP}$ $\mathsf{UP}$ $L$ $\mathsf{NP}$ $L$

Джошуа Грохов
источник