Есть ли известные проблемы в (а не в P ), которые не являются N P Complete? Насколько я понимаю, в настоящее время нет известных проблем, когда это так, но это не исключено как возможность.
Если есть проблема , которая является (а не Р ) , но не Н Р - с о м п л е т е , это было бы результатом не существующего изоморфизма между экземплярами этой проблемы и N Р - гр о м р л е т е множество? Если этот случай, как бы мы знаем , что N P проблема не является «тяжелее» , чем то , что мы в настоящее время определить , как N P - гр уплотнительного т р л х т множество?
complexity-theory
np-complete
p-vs-np
vpiTriumph
источник
источник
Ответы:
Нет, это неизвестно (за исключением тривиальных языков и Σ ∗ , эти два не являются полными из-за определения сокращений многие-один, обычно эти два игнорируются при рассмотрении сокращений многие-один). Существование проблемы N P, которая не является полной для N P по сравнению с многочленным сокращением времени за полином, подразумевает, что P ≠ N P, что неизвестно (хотя широко считается). Если эти два класса отличаются , то мы знаем , что существуют проблемы в N P , которые не являются полными для него, принимать какие - либо проблемы в P .∅ Σ∗ NP NP P≠NP NP P
Если два класса сложности различны , то по теореме Ладнер в существуют проблемы , которые являются -intermediate, то есть они находятся между P и N Р - с о т р л е т е .NP P NP-complete
Они по - прежнему полиномиальное время сводится к проблем , поэтому они не могут быть сложнее , чем N Р - с о т р л е т е проблем.NP-complete NP-complete
источник
Как сказал @Kaveh, этот вопрос интересен, только если предположить, что ; остальная часть моего ответа принимает это как предположение и в основном содержит ссылки для дальнейшего снижения аппетита. При этом предположении по теореме Ладнера мы знаем, что существуют проблемы, которых нет ни в P, ни в N P C ; эти проблемы называются N P -intermediate или N P I . Интересно, что теорема Ладнера может быть обобщена на многие другие классы сложности для получения аналогичных промежуточных задач. Далее, из теоремы также следует, что существует бесконечная иерархияп≠ Nп п NпС Nп Nпя промежуточных проблем, которые не являются поли-время приводимым друг с другом в .Nпя
К сожалению, даже с предположением очень трудно найти естественные задачи, которые были бы доказуемо N P I (конечно, у вас есть искусственные проблемы, вытекающие из доказательства теоремы Ладнера). Таким образом, даже если предположить, что P ≠ N P в это время, мы можем только верить некоторым проблемам, что N P I, но не доказать это. Мы приходим к таким убеждениям, когда у нас есть разумные доказательства того, что проблема N P не в N P C и / или не в PP≠NP NPI P≠NP NPI NP NPC P ; или просто когда его изучали в течение длительного времени и избегали вписываться в любой класс. В этом ответе есть довольно полный список таких проблем . Он включает в себя такие постоянные фавориты, как факторинг, дискретный лог и граф-изоморфизм.
Интересно, что некоторые из этих проблем (в частности, факторинг и дискретный лог) имеют полиномиальное время решения на квантовых компьютерах (то есть они находятся в ). Некоторые другие проблемы (такие как граф-изоморфизм), как известно, не находятся в B Q P , и есть продолжающиеся исследования, чтобы решить вопрос. С другой стороны, есть подозрение, что N P C ⊈ B Q P , поэтому люди не верят, что у нас будет эффективный квантовый алгоритм для SAT (хотя мы можем получить квадратичное ускорение); это интересный вопрос, чтобы беспокоиться о том, какая структура N P I проблемы нужны для того, чтобы быть в BBQP BQP NPC⊈BQP NPI BQP .
источник
Нет NP -полных проблемы , как известно, в P . Если для какой-либо задачи с NP- полным существует алгоритм за полиномиальное время , то P = NP , потому что любая проблема в NP имеет сокращение за полиномиальное время до каждой задачи с NP- полным. (Это на самом деле то, как определяется « NP- полный».) И, очевидно, если каждая проблема NP- полного находится за пределами P , это означает, что P ≠ NP . Мы не совсем уверены, почему трудно показать это так или иначе; если бы мы знали ответ на этот вопрос, мы, вероятно, знали бы намного больше о P иNP . У нас есть несколько методов доказательства, которые, как мы знаем, не работают (например, релятивизация и естественные доказательства), но у нас нет принципиального объяснения того, почему эта проблема сложна.
Если в NP есть проблемы, которых нет в P , то фактически существует бесконечная иерархия проблем в NP между задачами в P и теми, которые являются NP- полными: это результат, называемый теоремой Ладнера .
Надеюсь это поможет!
источник
Есть некоторые проблемы, которые являются NP, но никто не знает, что они являются NP-полными или , как изоморфизм графов 1 . Но, как я знаю, для таких проблем не существует специального класса сложности, может быть, я ошибаюсь.P
Может быть, это , например, до алгоритма AKS никто не знает, что тестирование простоты - это P или NPC.P P
1 Аналогичная проблема: изоморфизм подграфа является NP-полным в сильном смысле.
источник