Почему мы не можем перевернуть ответ NDTM эффективно?

Я прочитал несколько раз, что невозможно эффективно перевернуть ответ NDTM. Однако я не понимаю, почему. Например, учитывая NDTM который выполняется в , этот текст (раздел 3.3) утверждает, что неясно, как другой NDTM может определить за время, как перевернуть ответ$M$$O(n)$$T$$O(n^{100})$$M$

Моя проблема заключается в следующем: NDTM выводит если существует последовательность недетерминированных выборов, которая приводит к принимающему состоянию. Кроме того, существует универсальный NDTM который может моделировать каждый NDTM только с небольшими (логарифмическими) издержками. Итак, почему мы не можем построить T следующим образом: во-первых, смоделируйте M с универсальным NDTM, который должен быть возможен за время . Затем выведите 1 - ответ М. Это будет означать, что мы можем перевернуть ответ любого линейного NDTM за время .$1$$NU$$O(n\log n)$$O(n\log n)$

Недетерминированная машина Тьюринга принимает, если хотя бы один путь принимает; он только отклоняет, если отклоняются все пути. Эта асимметрия затрудняет "перевернуть ответы".

Например, предположим, что у вас есть недетерминированная машина Тьюринга  которой есть два пути для ввода  : один принимает, другой отклоняет.  есть по крайней мере один принимающий путь для  , поэтому он принимает. Предположим, мы хотим создать машину, которая принимает именно те входные данные, которые  отклоняет. Очевидная первая попытка состоит в том, чтобы взять  и заставить его принимающие состояния отклонить, а его отклоняющие состояния принять.  имеет один принимающий путь для  и один отклоняющий путь; эта новая машина  имеет один отклоняющий путь и один принимающий путь. Так что он по-прежнему принимает  , который он должен был отклонить!$M$$w$$M$$w$$M$$M$$M$$w$$M'$$w$

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

Когда вы моделируете недетерминированную машину  используя другую, , каждый путь  моделирует один путь  и видит только этот путь. Он не может сказать: «Если все эти другие пути отклонены, я приму», потому что он не может видеть другие пути; оно может видеть только себя. Поэтому все, что он может сказать, это такие вещи, как «Если путь, который я смоделировал, принят, я отклоню» или «Если путь, который я смоделировал, принял, я тоже приму». Затем в конце вычисления машина должна сказать: «Если какой-либо из моих путей будет принят, я тоже приму», что приведет к проблеме, которую я описал выше. Чтобы инвертировать поведение , каждый путь$M$$M'$$M'$$M$$M$$M'$нужно сказать: «Если путь, который я смоделировал, принят, я отклоняю; иначе я принимаю», и в конце вычисления машина должна сказать: «Если все мои пути приняты, я принимаю; в противном случае я отклоняю «. Это происходит потому , что, если все дорожки тренажера принято, что означает , что все путей «s отклонено, так отвергнуто, поэтому потребности тренажерных принять. Но симулятор не является действительной недетерминированной машиной Тьюринга, потому что он не использует юридически обязательный критерий приемлемости. Это не может сделать это.$M$$M$

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

Проблема заключается в том, что NDTM по своей природе несимметричны: время означает, что у них есть шагов, чтобы угадать принимающий путь, если он существует, и отклонит иначе (если не существует принимающего пути).O ( n $O(n)$$O(n)$

Проблема заключается в том, что если вашей машины действительно находится в , это означает, что он догадывается за шагов, свидетель, что отклоняет ввод. Это может быть невозможно сделать, потому что нет свидетелей отказа от , только свидетелей принятия. Отказ - это отсутствие свидетеля, поэтому нелегко доказать его в короткие сроки.O ( n l o g ( n ) ) n l o g ( n ) M $NU$$O(n log( n))$$n log (n)$$M$$M$

фактически технически вы задаете открытый вопрос о P coNP ( NP). это широко предположено, но не доказано, что они не равны. другие ответы - интуитивные наброски / косвенные доказательства того, что они не равны.? $\stackrel{?}{=}$$\stackrel{?}{=}$