Недостаток в моем NP = CoNP Доказательство?

12

У меня есть это очень простое «доказательство» для NP = CoNP, и я думаю, что где-то сделал что-то неправильно, но я не могу найти, что не так. Кто-нибудь может мне помочь?

Пусть A - некоторая проблема в NP, и пусть M - решающий фактор для A. Пусть B - дополнение, т. Е. B в CoNP. Поскольку M является решающим фактором, вы также можете использовать его для определения B (просто переверните ответ). Не значит ли это, что мы решаем проблемы NP и CoNP с одним и тем же M?

Проще говоря.

Пусть A некоторая NP-полная задача, и пусть M будет решающим для A. Рассмотрим любую проблему B в CoNP. Мы рассматриваем его дополнение не-B, которое находится в NP, и затем получаем полиномиальную редукцию к A. Затем мы запускаем наш решатель M и переворачиваем наш ответ. Таким образом, мы получаем решение для B. Это означает, что B также находится в NP.

Могу ли я знать, что не так с моими рассуждениями?

complexity-theory p-vs-np check-my-proof np простак
источник

2

Как подробно объясняют ответы ниже, вы не правильно используете понятие «решающий фактор». Проблемы в coNP не связаны с «перевернутым NP decider». Существует важная асимметрия в задачах NP между принятием ввода («существуют недетерминированные выборы, которые ведут к принятию») и отклонением его («все недетерминированные выборы ведут к отклонению»). Ваш аргумент предполагает, что для NP отклонение строки означает («есть недетерминированный выбор, который приводит к отклонению»), и это является недостатком. Другими словами, ваши квантификаторы перепутаны.

Андрей Бауэр

1

Вы можете найти ответы на этот вопрос поучительно.

Рафаэль

@Raphael Удивительно, но этот вопрос вообще не упоминает co-NP! (Хотя я согласен, что это полезное чтение для тех, кто не уверен в подобных

вещах

@DavidRicherby Поскольку ответ, в основном, «использовать определение NP вместо испорченной интуиции», я бы на это надеялся!

Рафаэль

1

Основное правило: конструкция «перевернуть конечные состояния» работает только для детерминированных моделей. Изучите, как НФА не может понять, почему. Смотрите также здесь и здесь .

Рафаэль

16

В этом доказательстве есть две возможные ошибки:

Когда вы говорите «решающий» - вы имеете в виду детерминистическую ТМ. В этом случае лучший перевод (насколько нам известно) из NP-машины в детерминированную машину может дать машину, которая работает в экспоненциальном времени, поэтому после дополнения у вас будет решающее слово для дополнения в экспоненциальном времени, доказывающее, что (или, после некоторой оптимизации, ). $co-NP\subseteq EXP$ $co-NP\subseteq PSPACE$
Когда вы говорите «решающий», вы имеете в виду недетерминированный ТМ. В этом случае перелистывание ответа не обязательно дополнит язык. Действительно, языком перевернутой машины будут все слова, для которых существует отбрасывающий прогон на $M$ $w$

Shaull
источник

Я не уверен, почему это важно. Мое определение принятия решения заключается в том, что я принимаю, если входное значение находится в L, и отклоняю, если входное значение не находится в L. Это решение может быть детерминированным или недетерминированным. Тем не менее, я говорю, что L находится в NP, и, следовательно, если я использую недетерминированную TM, я возьму полиномиальное время. Кроме того, могу я знать, почему переключение бита не обязательно дополняет язык. Насколько мне известно CoNP = {L | не L \ in NP}. Поэтому, если я переверну бит, я должен получить ответ?

Пусть . Рассмотрим недетерминированный TM, который работает следующим образом - за один прогон он всегда выдает «reject». В других прогонах он распознает за полиномиальное время (возможно, так как ). Подумайте, что произойдет, если вы перевернете бит - прогон отклонения становится приемлемым для каждого ввода, поэтому дополняемый компьютер распознает - который не является дополнением, если только . Я предлагаю вам пересмотреть определения недетерминизма, чтобы полностью это понять.

L \in N P

$L\in NP$

L

$L$

L \in N P

$L\in NP$

Σ^{*}

$\Sigma^*$

L = \emptyset

$L=\emptyset$

Шаул

Я не имею в виду, что я переворачиваю бит каждого пути вычислений. Я имею в виду, что если мой TM принимает, то это означает, что существует путь вычисления, который достигает состояния принятия. Это означает, что L находится в NP, что означает, что дополнение находится в coNP. Если моя TM отклоняет, это означает, что каждый вычислительный путь отклоняется. Это означает, что дополнение находится в NP, что означает, что L находится в CoNP.

4

@simpleton: Вы знаете, что NTM не имеет доступа ко всем путям одновременно, только к одному пути? Вы думаете, как кто-то, кто детерминистически анализирует поведение NTM извне.

frafl

7

Я думаю, что ФП может выиграть от более тщательного изучения определения НП.

МЧ

15

Вот еще один способ взглянуть на точку зрения Шаула относительно «решающих».

Проблема в NP тогда и только тогда, когда существует алгоритм такой, что $V: \{0,1\}^n \times \{0,1\}^{\mathrm{poly}(n)} \to \{0,1\}$

для каждого экземпляра YES существует сертификат такой, что ; и $x \in \{0,1\}^n$ $p \in \{0,1\}^{\mathrm{poly}(n)}$ $V(x,p) = 1$
для каждого экземпляра NO мы имеем для всех , $x \in \{0,1\}^n$ $V(x,p) = 0$ $p \in \{0,1\}^{\mathrm{poly}(n)}$

Они обычно описываются как условия полноты и надежности для алгоритма проверки NP : условие «полноты» говорит о том, что каждый экземпляр YES имеет сертификат, а условие «обоснованности» говорит о том, что алгоритм никогда не обманывается экземпляром NO. Для coNP все наоборот: есть алгоритм верификатора, который примет хотя бы один сертификат для любого экземпляра NO, но который никогда не может быть обманут экземпляром YES.

Если вы хотите показать, что NP ⊆ coNP , вы должны показать, что у каждой проблемы NP есть верификатор типа coNP , который может сертифицировать НЕТ экземпляров вместо ДА. Вы не можете сделать это с помощью недетерминированной машины Тьюринга: мы не знаем, как, например, эффективно отобразить экземпляры SAT друг на друга таким образом, чтобы все неудовлетворительные формулы отображались в выполнимые, и наоборот, (Отрицательного результата вывода формулы недостаточно, например: формула, которая является выполнимой, но не тавтологической, будет просто сопоставлена с другой формулой, которая была бы выполнимой, но не тавтологией, когда вместо этого нам понадобится неудовлетворительная формула.) Мы просто не знаем, как «обмануть» недетерминированную машину, чтобы обнаружить, что все ее пути являются отклоняющими.

Вы можете спросить: «Разве недетерминированная машина Тьюринга не знает, какой результат она получает?» Ответ будет нет , это не имеет. Работа недетерминированной машины не дает ей доступа к какой-либо информации о более чем одном вычислительном пути одновременно: вы можете подумать, что она работает во многих путях параллельно, но внутри каждого пути она знает только об этом одном пути. Если вы попытаетесь наделить его способностью «осознать», существуют ли какие-либо решения в качестве некоторого пункта, вы вместо этого описываете машину с оракулом NP , которая является более (потенциально!) Мощной, чем простая недетерминированная машина Тьюринга.

Например, если вы оснащать (детерминированный) машина Тьюринга с NP оракула, то проблемы , которые могут быть решены за полиномиальное время на этой машине называется , который часто пишется . «Оракул» позволяет машине просто получать ответы на NP- неполные задачи за один шаг, и поэтому очевидно, содержит P ; и потому что вы можете отрицать ответы, он также, очевидно, содержит coNP . Но мы не знаем, имеет ли место обратное сдерживание, именно потому, что мы не знаем, как обмануть недетерминированные машины Тьюринга в обнаружении НЕТ ответов. $\Delta_2^{\mathrm P}$ $\mathsf{P}^{\mathsf{NP}}$ $\mathsf{P}^{\mathsf{NP}}$
Более того, если вы дадите недетерминированной машине Тьюринга возможность прийти к осознанию результата проблемы в NP , проблемы, которые эта машина может решить за полиномиальное время, называются или , и считается, что это строго больше, чем класс . Он также содержит как NP, так и coNP - но, как и NP , он не известен как закрытый под дополнениями: недетерминированная машина оракула могла бы знать, когда проблема в NP $\Sigma_2^{\mathrm P}$ $\mathsf{NP}^{\mathsf{NP}}$ $\mathsf{P}^{\mathsf{NP}}$ не имеет ответа из-за оракула, но он все равно будет зацикливаться на работе внутри одной из своих (довольно мощных) вычислительных ветвей, так что он не сможет определить, отклоняются ли все его собственные вычислительные ветви.

Если вы продолжаете снабжать машину более мощными оракулами для решения задач в , и т. Д., Вы в конечном итоге определяете классы полиномиальной иерархии , которые считаются отличными друг от друга, начиная с первого уровня. $\mathsf{NP}$ $\mathsf{NP}^{\mathsf{NP}}$

Итак, нет, не существует машины (детерминированной или иной), которая могла бы просто «решить», что проблема - это ДА или НЕТ, если мы не будем использовать оракулы; но даже с таким оракулом мы в конечном итоге получим машину, которая (вероятно) более мощна, чем NP или coNP , а не такую , которая показывает, что они равны.

Ниль де Бодрап
источник

Привет, спасибо тебе и Шаули за комментарии. Вы говорите, что NTM может распознавать язык NP в polytime, но не может определить язык NP в polytime? Я думаю, что это то, что я предполагаю, когда говорю, что у меня есть решение проблем NP.

простак

2

О, я думаю, что понимаю, что ты имеешь в виду. Вы говорите, что я использую сокращение оракула, и это фактически показывает, что проблема в (что верно, потому что и )? Сокращение оракула показывает, что UNSAT является NP-сложным, но мне все еще нужно показать, что , и я не могу показать это?

P^{N P}

$P^{NP}$

N P \subset P^{N P}

$NP \subset P^{NP}$

C o N P \subset P^{N P}

$CoNP \subset P^{NP}$

U N S A T \in N P

$UNSAT \in NP$

простак

5

NP-твердость определяется многими сокращениями, а не оракулами.

Юваль Фильмус

6

Ваше рассуждение подразумевает, что RE = coRE, но это доказуемо ложно. Вы можете попытаться найти подтверждение этому, а затем посмотреть, где ваше снижение не удается.

Напомним, что RE - это класс сложности рекурсивно перечислимых языков, которые являются языками вида . Вы также можете думать об этом недетерминированными терминами: RE - это класс языков вида , где рекурсивно ( вычислимая). $\{ x : P \text{ halts on input } x \}$ $\{ x : (x,w) \in L' \text{ for some } w \}$ $L'$

Вот доказательство того, что оба определения совпадают. Предположим, сначала . Пусть . Язык является рекурсивным и . $L = \{ x : p \text{ halts on input } x \}$ $L' = \{ (x,w) : p \text{ halts on input } x \text{ in } w \text{ steps} \}$ $L'$ $L = \{ x : (x,w) \in L' \text{ for some } w \}$

Для другого направления пусть , где рекурсивно, скажем, вычислено программой . Мы строим новую программу которая перечисляет все возможные и запускает на всех по порядку. Если когда-либо принимает для некоторого , то останавливается. Нетрудно проверить, что . $L = \{ x : (x,w) \in L' \text{ for some } w \}$ $L'$ $P(x,w)$ $Q(x)$ $w$ $P(x,w)$ $w$ $P(x,w)$ $w$ $Q$ $L = \{ x : Q \text{ halts on input } x \}$

Для вашего удобства здесь приведены схемы доказательства того, что RE отличается от coRE. Язык явно рекурсивно перечислим: программа для него просто запускает на . Предположим , что программа была такая , что останавливается , если и только если . Определим новую программу помощью . Является ли ? Если это так, то привалы на , так привалы на , так . Если , то $L = \{(P,x) : P \text{ halts on input x}\}$ $P$ $x$ $H$ $H(P,x)$ $(P,x) \notin L$ $G$ $G(x)=H(x,x)$ $(G,G) \in L$ $G$ $G$ $H$ $(G,G)$ $(G,G) \notin L$ $(G,G) \notin L$ $G$ не останавливается на , поэтому не останавливается на , так . Это противоречие показывает, что не может существовать. $G$ $H$ $(G,G)$ $(G,G) \in L$ $H$

Теперь попробуйте запустить ваше доказательство в этом случае и посмотреть, что идет не так. Более подробно, попытайтесь сконструировать программу используя ваш рецепт, и следуйте доказательству - в какой-то момент что-то будет не совсем правильным. $H$

Юваль Фильмус
источник

2

Вот версия TL; DR; Я также опубликовал более длинный ответ на аналогичный вопрос.

Предположим , у нас есть язык , который решил в полиномиальное время недетерминированными машины Тьюринга . Дело в том, что тогда и только тогда, когда имеет некоторый принимающий путь на входе . Однако, поскольку недетерминировано, могут также быть отклонения путей, когда он работает на $A$ $M$ $x\in A$ $M$ $x$ $M$ $x$ , Если вы просто поменяете местами принимающий и отклоняющий состояния, вы перейдете с машины, на которой есть несколько принимающих и отклоняющих путей, к машине, на которой есть несколько отклоняющих и принимающих путей. Другими словами, он все еще имеет принимающие пути, поэтому он все еще принимает. Переключение состояний принятия и отклонения недетерминированной машины, как правило, не заставляет вас принять язык комплемента.

Именно эта асимметрия определения (примите, если любой путь принимает; отклоните, только если все пути отклонены), что делает проблему NP против co-NP трудной.

Дэвид Ричерби
источник

-2

Я на самом деле согласен, что ваша недетерминированная машина M может решить, находится ли данная входная строка в B. Однако она «решает» немного иначе, чем то, как она решает, находится ли данный вход в A. В последнем случае она делает это посредством ( недетерминированно) нахождение принимающего государства. В первом случае это происходит из-за невозможности найти принимающие состояния. Почему эта разница имеет значение? Посмотрим:

Когда спрашиваешь М "Есть ли строка на языке А?"

М достигает состояния принятия. Это, как вы можете доказать (см., Например, теорему 7.20 из книги Сипсера), подразумевает, что существует детерминированная машина, которая проверяет, находится ли строка в A за полиномиальное время

Когда спрашиваешь M "Строка на языке B?"

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

Вывод:

Если вы считаете, что наличие детерминированного верификатора за полиномиальное время для языка является определением языка NP (что вам следует), существование M не доказывает, что B находится в NP.

Alex
источник

1

Существование не доказывает , что находится в NP именно потому , что вы должны использовать этот критерий «странно» приемочного , чтобы сделать его «принять» . NP определяется с помощью обычного недетерминированного критерия приемлемости. (Критерий приемлемости немного странный, отчасти потому, что вопрос говорит о том, чтобы изменить принятие и отклонение состояний в но вы, похоже, этого не сделали.)

M

$M$

B

$B$

B

$B$

M

$M$

David Richerby

Недостаток в моем NP = CoNP Доказательство?

Ответы:

Когда спрашиваешь М "Есть ли строка на языке А?"

Когда спрашиваешь M "Строка на языке B?"

Вывод: