Почему эта неразрешимая проблема в NP?

25

Очевидно, что в NP нет неразрешимых проблем. Однако, согласно Википедии :

NP - это совокупность всех задач решения, для которых в случаях, когда ответ «да», есть [... доказательства, которые] проверяются за полиномиальное время с помощью детерминированной машины Тьюринга.

[...]

Говорят, что проблема в NP, если и только если существует верификатор для задачи, которая выполняется за полиномиальное время.

Теперь рассмотрим следующую проблему:

Имеет ли диофантово уравнение , есть ли у него целочисленные решения?

Учитывая решение, легко за полиномиальное время проверить, что оно действительно является решением: просто вставьте числа в уравнение. Таким образом, проблема в NP. Однако известно, что решение этой проблемы неразрешимо !

(Точно так же кажется, что проблема остановки должна быть в NP, поскольку «да» - решение «эта программа останавливается на N-м шаге» может быть проверено за N шагов.)

Очевидно, что-то не так с моим пониманием, но что это?

BlueRaja - Дэнни Пфлугхофт
источник
1. Имейте в виду, что приведенное вами определение относится к решению проблем. 2. Что касается вашего диофантова примера, вы не утверждаете, что в каждой системе существует полиномиальная зависимость от размера решений, верно?
Дмитрий Чубаров
@Dmitri: Er, да, я утверждаю это. Размер решения точно такой же, как размер задачи - если имеется N неизвестных, решение содержит N целых чисел. И это является проблемой , решение - целое решение (нужно проверить «да» случай) будет его сертификат .
BlueRaja - Дэнни Пфлюгофт
19
Вопрос в том, насколько велики эти интеграторы
Артем Казнатчеев
10
@ BlueRaja-DannyPflughoeft Если у вас есть бесконечный алфавит для кодирования ваших целых чисел, то вы больше не находитесь в стандартной настройке теории сложности. С конечным алфавитом размер кодировки увеличивается со значением целого числа.
Дмитрий Чубаров
Решение проблемы остановки просто вернет «Да», без подсказки, сколько шагов имитировать для проверки.
RemcoGerlich

Ответы:

10

Эквивалентное определение NP состоит в том, что он состоит из всех задач, которые разрешимы (а не просто проверяемы) за полиномиальное время с помощью недетерминированной машины Тьюринга. Известно, что NTM не более мощны, чем ТМ, в том смысле, что набор проблем, решаемых НТМ, идентичен набору задач, решаемых ТМ, поэтому ясно, что по этому определению не может быть неразрешимых проблем в NP.

Чтобы продемонстрировать, что два определения NP эквивалентны, учитывая наличие детерминированного верификатора, вы можете продемонстрировать, что существует недетерминированный решатель, и наоборот.

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

Если у вас есть недетерминированный решатель, то для каждого принимающего вычисления вы можете записать путь выбора, принятого решателем, чтобы достичь состояния принятия. Поскольку решающий блок выполняется за полиномиальное время, длина этого пути будет максимально полиномиальной. И для детерминированной TM легко проверить, что такой путь является допустимым путем через NTM до состояния принятия, поэтому такие пути образуют сертификаты для полиномиального верификатора времени для проблемы. Таким образом, существует детерминированный верификатор для каждого недетерминированного решателя.

Таким образом, любая неразрешимая проблема не может иметь верификатора, который работает с сертификатами полиномиального размера (в противном случае наличие верификатора подразумевало бы существование решающего элемента).


Когда вы утверждаете, что существует верификатор для проблемы остановки, сертификат, о котором вы говорите, является некоторой кодировкой (TM, I, N), где TM останавливается на входе I за N шагов. Это действительно может быть проверено за N шагов, но размер сертификата не является полиномиальным по отношению к размеру (TM, I) входных данных для исходной проблемы (проблема остановки); N может быть сколь угодно большим (независимо от кодировки). Если вы попытаетесь преобразовать такой верификатор в недетерминированный решатель, вы получите довольно интересную машину. Вы должны быть в состоянии доказать, что при запуске на (TM, I) для TM, который неостановка на входе I не существует не прерывающихся путей через машину, но также и то, что для любого пути, приводящего к состоянию остановки, всегда есть другой более длинный путь (соответствующий предположению большего N), и, таким образом, нет конечной границы для время его исполнения. По сути, это потому, что существует бесконечное пространство, которое необходимо исследовать с помощью первоначального недетерминированного предположения. Преобразование такого NTM в детерминированный TM приводит к одной из тех машин, которая не зацикливается и не останавливается на некотором входе. Фактически не существует NTM, который мог бы решить проблему остановки, и поэтому не существует верификатора, который работал бы с сертификатами с ограниченным размером.

Я не очень знаком с диофантовыми уравнениями, но похоже, что по сути та же самая проблема применима к вашей аргументации.

По этой причине мне проще рассуждать об определении NTM NP. Существуют верификаторы для неразрешимых проблем (только те, которые работают с сертификатами, размер полинома которых связан с размером входных данных исходной задачи). Фактически любой TM, который распознает, но не решает какой-либо язык, может быть легко преобразован в верификатор для того же языка.

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

Бен
источник
26

Я думаю, вы неправильно поняли, что значит решить диофантово уравнение и теорему Матиясевича о неразрешимости .

Матиясевич доказал, что для каждого RE-множества существует диофентинное уравнение такое, что только если существуют целочисленные коэффициенты , .., такие, что . В частности, проблема остановки является типичным набором RE, и поэтому решение вышеуказанной проблемы неразрешимо.е ( п , х 1 , . . . , Х к ) п S х 1 х к е ( п , х 1 , . . . , Х к ) = 0Sf(n;x1,...,xk)nSx1xkf(n;x1,...,xk)=0

Обратите внимание, что не ограничены по размеру и, как правило, могут быть произвольно большими, поэтому в этой задаче нет «сертификата полиномиального размера».x1,...xk

Для расширения: целые числа должны быть записаны в двоичном виде, чтобы быть сертификатом. Поскольку эти целые числа могут быть сколь угодно большими (независимо от ), мы имеем, что сертификат не является полиномом в или, что более важно, не ограничен и вычислимой функцией. n log nx1,...,xknlogn

Однако каждая проблема в имеет сертификат, ограниченный каким-то полиномом (где - размер ввода). Таким образом, вопросы тривиально разрешимы, так как вы можете перечислить каждую возможную битовую строку до длины и, если ни один из них не подтвердит ввод, верните false. Если что-то есть, верните true. п ( Н ) Н Н П п ( Н )NPp(N)NNPp(N)

Артем Казнатчеев
источник
Конечно, я понимаю, что значит «решить диофантово уравнение» - вы найдете числа, которые удовлетворяют уравнению. Я не понимаю, почему теорема Матиясевича о неразрешимости или рекурсивно перечислимые множества должны быть включены в дискуссию. Но я думаю, что последний абзац может объяснить это ...
BlueRaja - Дэнни Пфлюгофт
1
Хорошо, это новое редактирование объясняет это - это также объясняет, почему проблема с остановкой отсутствует в NP, поскольку шаги, необходимые для остановки, могут быть сколь угодно большими. Благодарность!
BlueRaja - Дэнни Пфлюгофт
Мое предлагаемое изменение должно было удалить первые два параграфа. Первые два параграфа объясняют, почему 10-я проблема Гильберта неразрешима, что является совершенно касательным к вопросу; они просто отвлекают от остальной части ответа (в противном случае это отличный ответ!) .
BlueRaja - Дэнни Пфлюгофт
@ BlueRaja-DannyPflughoeft, если первый абзац оскорбил вас, тогда я могу удалить его (хотя вы спрашивали «что не так с моим пониманием?»). Второй абзац необходим для того, чтобы решить проблему более формально, поскольку вы не отвечаете на свой вопрос.
Артем Казнатчеев
3
@ BlueRaja-DannyPflughoeft Лучше всего, если вопросы и ответы будут автономными. Мой второй абзац устанавливает проблему и объясняет, что означает ее неразрешимость. Мой третий абзац дает быстрый ответ. Мои 4-й и 5-й абзацы раскрывают это более подробно. Насколько я могу сказать, все параграфы необходимы.
Артем Казнатчеев
8

Вы должны были прокрутить до формального определения :

Язык находится в NP тогда и только тогда, когда существуют полиномы и , и детерминированная машина Тьюринга , такая чтоp q MLpqM

  • Для всех и y машина работает в момент времени на входе .M p ( | x | ) ( x , y )xMp(|x|)(x,y)
  • Для всех существует строка длины такая, что .y q ( | x | ) M ( x , y ) = 1xLyq(|x|)M(x,y)=1
  • Для всех и всех строк длины , .y q ( | x | ) M ( x , y ) = 0xLyq(|x|)M(x,y)=0

То есть верификатор должен работать и с не-решениями. Где-то там неразрешимые проблемы терпят неудачу (в вашем случае ограничение длины кандидатов на решения, вероятно, не выполняется), что очевидно из (более четкого определения (в смысле вычислимости) :

NP - это набор задач, решаемых недетерминированной машиной Тьюринга, работающей за полиномиальное время.

Рафаэль
источник
«верификатор должен работать и с не-решениями» - если вы говорите, что верификатор должен потерпеть неудачу для не-решений, это уже происходит. Если вы утверждаете, что верификатор должен иметь возможность проверять ответы «нет», это неверно - это будет co-NP . И я уже знаю о втором определении, но меня смутило то, как оно может быть эквивалентно первому, поскольку одно определение, похоже, допускает проблему в вопросе, а другое - нет.
BlueRaja - Дэнни Пфлюгофт
@ BlueRaja-DannyPlughoeft: Мое наблюдение таково: верификаторы должны иметь возможность опровергать не решения. Если вам это известно, отредактируйте ваш вопрос соответствующим образом; это заставляет вас выглядеть совершенно неизвестным.
Рафаэль
Очевидно, что верификатор уже опровергает нерегулярные решения: просто вставьте числа в уравнение и посмотрите, верно ли оно. Боюсь, я не понимаю, к чему ты клонишь.
BlueRaja - Дэнни Пфлюгофт
@ BlueRaja-DannyPlughoeft: указанное вами «определение» не определяет это поведение.
Рафаэль
-1

Я пытаюсь предоставить более подробную информацию для моего ответа выше.

На самом деле, этот вопрос является проблемой дилеммы.

С одной стороны, проблема диофантовых уравнений (DEP) неразрешима в соответствии с теоремой Матиесевича (теорема Матиесевича отвечает на десятую проблему Гильберта, а проблема Тьюринга - Остановка отвечает на обобщение десятой проблемы Гильберта, то есть проблемы Энтшайдунга); но с другой стороны, нет никакой неразрешимой проблемы в NP согласно определению NP (разрешимой и проверяемой).

То есть, либо DEP не в NP, либо DEP в NP. Оба они касаются определения NP.

Если DEP отсутствует в NP, это означает, что проблемы в NP (NDTM = Недетерминированная машина Тьюринга) разрешимы и проверяемы, то есть мы принимаем P = NP (NDTM).

Если DEP находится в NP, то NP (NTM = Non Turing Machine) содержит разрешимые и неразрешимые, очевидно разрешимые поддается проверке, поэтому проблема в том, поддается ли проверке неразрешимая? На самом деле, это знаменитая проблема P против NP. Конечно, неразрешимое не подлежит проверке, поэтому NP соответствует NTM (Машина Тьюринга), а не NDTM (Машина недетерминированного Тьюринга).

Исходя из того, что DEP находится в NP (NTM), мы думаем, что NP (NTM) является недетерминированной проблемой (неразрешимой), и текущее определение NP (NDTM, разрешимое и проверяемое) утратило эту недетерминированность (неразрешимую), поэтому мы думаем, что это должно быть подвергнуто сомнению.

Ю Ли
источник
1
Нет, неразрешимость DEP (десятая проблема Гильберта) не была показана Матиесевичем до 1970 года. Проблема Энтшейдуна не является десятой проблемой Гильберта; касается правильности формул логики первого порядка. И, опять же, проблема P против NP абсолютно не проблема о том, являются ли неразрешимые проблемы проверяемыми.
Дэвид Ричерби
1
Если вы хотите предоставить более подробную информацию, вам следует отредактировать исходное сообщение.
Том ван дер Занден
@DavidRicherby Обратите внимание, что ответ, данный Беном: «множество проблем, решаемых с помощью NTM, идентично набору проблем, решаемых с помощью TM». Именно в этом смысле я думаю, что определение NP путает P с NP, и это приводит к P = NP (NDTM). Если это определение необходимо подвергнуть сомнению, то должны быть подвергнуты сомнению и другие выводы, сделанные из этого определения, такие как эквивалентность детерминированного верификатора и недетерминированного решающего фактора.
Ю Ли
@YuLi "это приводит к P = NP (NDTM)." Понятия не имею, что вы подразумеваете под этим. Кроме того, я не вижу смысла указывать, что ТМ и НТМ выбирают одни и те же языки. Если бы они не выбирали одни и те же языки, NTM были бы совершенно неразумной моделью вычислений, и трудно представить, что нам будет интересно, что они смогут вычислить за полиномиальное время. В теории сложности мы придерживаемся более детального взгляда и спрашиваем о необходимых вычислительных ресурсах, а определение NP вообще не смущает это.
Дэвид Ричерби
@DavidRicherby Спасибо, я изменил свой ответ в соответствии с вашим замечанием, чтобы прояснить связь проблемы Энтшайдунгса и десятой проблемы Гильберта. Что касается вопроса о текущем определении NP, то его трудно обсудить в нескольких словах. Цель моего ответа - просто вызвать некоторые размышления об этой основной теме…
Ю Ли Ли
-2

Мы думаем, что дилемма, которую вы подняли в отношении диофантова уравнения, очень важна, потому что она обнаруживает что-то ненормальное в текущем определении NP: - Говорят, что проблема в NP, если и только если существует верификатор для задачи, которая выполняется в полиноме время.

Что касается определения NP, его можно проследить до 60-х годов, когда было обнаружено большое количество применимых и значительных проблем, для которых не было найдено ни одного полиномиального алгоритма для их решения, чтобы распознать эти проблемы по тем проблемам, которые можно решить за полиномиальное время. (P), концепция NP была выпущена.

Однако текущее определение NP, определяемое как проверяемое за полиномиальное время, путает NP с P, поскольку проблема в P также проверяется за полиномиальное время. Иными словами, такое определение приводит к утрате сущности НП, «недетерминизма». Следовательно, это вызывает серьезные двусмысленности в понимании NP, например, вашей дилеммы: по своей природе проблема диофантова уравнения неразрешима; но по определению NP, это разрешимо, ...

По нашему мнению, сложность решения «P против NP» лежит, в первую очередь, на уровне познания, поэтому, если мы надеемся получить представление о «P против NP», нам нужно сначала задать вопрос: что такое NP?

Ю Ли
источник
4
Похоже, что это часть мнения об определении NP , а не ответ на вопрос. Определение NP просто отлично. Это не путает P с NP ; скорее это признает, что P является подмножеством NP . Для меня было бы очень неестественно, если бы P не был подмножеством NP . NP - это класс проблем, которые могут быть решены в определенных пределах ресурсов. Это обязательно включает в себя целый ряд простых проблем ( P ), которые можно решить, не приближаясь к пределу доступных ресурсов.
Дэвид Ричерби
@DavidRicherby P и NP имеют общее свойство «сертификат проверяется за полиномиальное время», но это свойство не является сущностью NP. Если это свойство используется для определения NP, то P является подмножеством NP, и NP имеет P в качестве своего подмножества (разрешимого) и самого себя (неразрешимого). Следовательно, можно задаться вопросом, является ли NP разрешимым или неразрешимым? Точно так же как вышеупомянутая дилемма: является ли диофантово уравнение неразрешимым или разрешимым? Таким образом, мой ответ состоит в том, чтобы предложить исследовать эту дилемму с точки зрения определения NP: проверяемый, неразрешимый непроверяемый!
Ю Ли
Проблемы в НП разрешимы по определению: NP является классом задач решили недетерминированными машины Тьюринга. Легко доказать, что это точно такой же набор задач, которые имеют сертификаты полиномиальной длины, которые можно проверить за полиномиальное время. Если вы беспокоитесь о том, что проблемы в NP могут быть не решаемыми, то вы что-то неправильно поняли.
Дэвид Ричерби
Да, я обеспокоен тем, что проблемы в NP не могут быть решаемыми. Вы говорите об эквивалентности двух определений NP: NP - класс задач, решаемых недетерминированными машинами Тьюринга; NP - класс задач, имеющих сертификаты полиномиальной длины, проверенные за полиномиальное время. Я сомневаюсь в этой эквивалентности, потому что один о существовании алгоритма для решения проблемы, а другой о существовании решения для проблемы. Дилемма о диофантовом уравнении может быть напрямую связана с этой эквивалентностью (см. Более подробную информацию о моем аргументе: arxiv.org/abs/1501.01906 ).
Ю Ли
2
@YuLi Эквивалентность двух определений NP настолько проста, что преподается на уроках теории сложности для студентов. Я предлагаю не загружать в ArXiv, если вы не понимаете основы поля.
Дэвид Ричерби