Является ли обязательным, чтобы «сокращение проблемы выполнялось за полиномиальное время», чтобы оно было полным?

Question

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

Теперь, если у нас есть только экспоненциальный алгоритм времени для сокращения. Будет ли эта проблема по-прежнему называться NP-complete? Или нет таких существующих проблем?

EDIT: Также, пожалуйста, сообщите мне, есть ли такая проблема, и существует ли она тогда, к какому классу она принадлежит?

Answer 1

Are such problems NP-complete? 

No. Доказательство:

Пусть ваша проблема = А.

Пусть NP-полной задачи он уменьшает в (по крайней мере) экспоненциальное время = B. "По крайней мере," потому что вы может сделать дополнительную тривиальную работу, чтобы добраться до экспоненциального времени, или следовать менее оптимальному подходу (чтобы доказать, что не существует более эффективной стратегии сокращения, вероятно, довольно сложно, возможно, в том же шаровом парке, что и N! = NP, который до настоящего времени не был решен).

Поскольку B является NP-полным, "every problem in NP is reducible to B in polynomial time".

Если A находится в NP, то оно должно быть полиномиально-временным, сводимым к B. Но это не так, поэтому оно не находится в NP.

Таким образом, он не может быть NP-полностью.

Проще говоря - любая проблема в NP должна быть не хуже, чем A, и это явно не так.

Are there such problems? 

Я думаю, это может быть такая проблема: (рекурсивный knapsack) (я не возражал бы комментарий или два, чтобы ли это кто-то умный)

Учитывая набор элементов, каждый с весом и значением, найти подмножество с максимальным общим весом A, а также найти подмножество внутри этого подмножества с некоторым максимальным общим весом C с целью максимизировать сумму значений двух подмножеств.

To which class does it belong? 

Я довольно уверен, что это не имя специально для них, но я думаю, что многие (или все?) Из них являются NP-hard. Доказательство: (по крайней мере, для вышеуказанной проблемы, считая, что это такая проблема)

Определение: "A problem H is NP-hard if ... (an NP-complete problem) L can be solved in polynomial time by an oracle machine with an oracle for H".

Предположим, что приведенный выше пример является такой проблемой и пусть оно = H. Предположим, у нас есть оракул, который может решить вышеизложенное в постоянное время. Но проблема с рюкзаком - это просто частный случай вышеуказанного (C = 0), поэтому мы можем решить проблему ранца в постоянное время (это полиномиальное время) с использованием оракула.

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

EDIT: О, похоже, у них действительно может быть имя, 2-EXPTIME.

Answer 2

Можно рассматривать только NP-complete, если другие NP-проблемы могут быть сведены к нему за полиномиальное время. Причина, по которой это полезное определение, состоит в том, что, если мы найдем алгоритм полиномиального времени для одного, он автоматически дает один для всех NP-проблем. Если бы мы допустили экспоненциальное сокращение времени, но нашли решение по полиномиальному времени для приведенной задачи, это фактически не помогло бы нам решить ту, к которой мы ее привели.

Надеюсь, это поможет.

Answer 3

Полнота теории сложности всегда определяется для определенного вида сокращений, иногда известных из контекста и, таким образом, не упомянутых явно. Известный класс NP-полных проблем определяется как полный для полиномиальных сокращений времени по причинам, указанным в ответе Ричарда Раста.

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

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

Answer 4

Как было отмечено намного раньше, направление вашего вопроса неверно. Задача А является NP-полной по определению, если каждая задача B в NP может быть уменьшена в полиномиальное время до задачи A. Поэтому я предполагаю, что ваш вопрос заключается в том, должно ли это сокращение быть в полиномиальном, а не экспоненциальном времени.

Если вы разрешили экспоненциальное сокращение времени: Возьмите следующую проблему решения X: «Является ли вход ДА?» Это почти самая простая проблема решения. Ответ - ДА, если входной сигнал YES, ответ НЕТ, если вход не является YES. Но каждая проблема в NP сводится к задаче X в экспоненциальном времени. Разумеется, мы не хотим называть проблему X «NP-complete». Поэтому экспоненциальное сокращение времени не допускается, поскольку это позволяет сделать термин «NP-complete» абсолютно бессмысленным.