Какие доказательства у нас есть для ?

Следуя предложению Джоша Грохова, я превращаю свой комментарий из предыдущего вопроса в новый.

Какие доказательства у нас есть для ? $\mathsf{UP} \neq \mathsf{NP}$

Здесь - это класс языков, распознаваемых недетерминированными машинами Тьюринга за полиномиальное время, которые имеют уникальный путь принятия в экземплярах "да" и нет пути принятия в экземплярах "нет". $\mathsf{UP}$

Очевидно, , но почему мы считаем, что сдерживание строго? Доказательством, которое я могу найти, является разделение оракула : случайный оракул, . Кроме того, зоопарк сложности предполагает, что как полагают, не имеет полных проблем. $\mathsf{UP} \subseteq \mathsf{NP}$ $\mathsf{P} \subsetneq \mathsf{UP} \subsetneq \mathsf{NP}$ $\mathsf{UP}$

cc.complexity-theory complexity-classes conditional-results unique-solution Сашо Николов
источник

Связанное обсуждение здесь: cstheory.stackexchange.com/q/3887/1800

Сянь-Чжи Чанг 之之

@ Hsien-ChihChang 之之 хм, может быть, мой вопрос повторяется. Если вы так думаете, я могу пометить его для удаления.

Сашо Николов

Я не думаю, что это дубликат. Я думаю, что ответы на другой вопрос будут считаться ответами на этот вопрос, но не обязательно наоборот - могут быть причины полагать, что , которые не имеют форму " Если , то возникают некоторые (иные) плохие последствия сложности ".

N P \neq U P

$\mathsf{NP} \neq \mathsf{UP}$

N P = U P

$\mathsf{NP}=\mathsf{UP}$

Джошуа Грохов

Наилучшим доказательством является то, что у нас есть субэкспоненциальные верхние границы для некоторых естественных неразрешимых задач в UP (таких как варианты решения дискретного логарифма и целочисленная факторизация), в то время как мы не можем найти такую верхнюю границу для некоторых NP-полных задач, таких как 3SAT. Такая верхняя оценка для 3SAT невозможна в предположении экспоненциальной временной гипотезы.

Мухаммед Аль-Туркистани

@ MohammadAl-Turkistany: Но эти проблемы находятся в , поэтому если , они все равно будут только в , поэтому не будет -комплектным, если только ...

U P \cap c o U P

$\mathsf{UP} \cap \mathsf{coUP}$

N P = U P

$\mathsf{NP} = \mathsf{UP}$

N P \cap c o N P

$\mathsf{NP} \cap \mathsf{coNP}$

N P

$\mathsf{NP}$

N P = c o N P

$\mathsf{NP} = \mathsf{coNP}$

Джошуа

Даже, Селман и Якоби высказал предположение , что не существует непересекающиеся -парой таким образом, чтобы все разделители являются -Жесткий для . Эта гипотеза предполагает , что . $NP$ $(A, B)$ $(A, B)$ $\le_T^p$ $NP$ $UP \ne NP$

С. Эвен, А. Сельман и Дж. Якоби. Сложность обещания проблем с приложениями к криптографии с открытым ключом. Информация и контроль, 61: 159–173, 1984.

Мухаммед Аль-Туркистани
источник

Это также работает как хороший ответ для соответствующего поста cstheory.stackexchange.com/questions/3887/…

Мохаммад Аль-Туркистани

Эта сильная гипотеза предполагает также , что

N P \neq c o N P

$NP \ne coNP$

Мухаммед Аль-Туркистани

Какие доказательства у нас есть для ?

Ответы: