Должна ли NP-полнота / твердость быть конструктивной?

11

Существует ли со следующими свойствами: $L\in {\bf NP}$

Известно , что влечет . $L\in {\bf P}$ ${\bf P}={\bf NP}$
Там нет (известного) полинома Тьюринга уменьшения (или какой -либо другой -полной проблемы) к . $SAT$ ${\bf NP}$ $L$

Другими словами, если полиномиальный алгоритм время для означает крах в , то это необходимо , чтобы эта «общая жесткость» из для должно быть каким - то образом в том смысле, что, скажем, должно быть приведено к посредством некоторого конкретного сокращения? $L$ ${\bf NP}$ ${\bf P}$ $L$ ${\bf NP}$ $constructive$ $SAT$ $L$

cc.complexity-theory np-hardness reductions Андрас Фараго
источник

10

Мне кажется, что название и текст задают два разных вопроса. Например, ответ Каве работает на вопрос в теле, но не на вопрос в заголовке.

Робин Котари

15

Да, есть такие наборы, возьмите любой -средний набор (любой набор, который является доказуемо -средним, предполагающим ), например, построите один из SAT, используя теорему Ладнера. $\mathsf{NP}$ $\mathsf{NP}$ $\mathsf{P}\neq\mathsf{NP}$

Обратите внимание, что ваш должен учитывать промежуточную проблему , поскольку он находится в но не завершен для нее. Отметим также , что вы предполагая , что иначе нет таких , как каждая нетривиальная задача была бы полной для , если . Кроме того, условия, которые вы задали, не подразумевают полноты, поэтому вопрос в первой части не совпадает с вопросом о конструктивности полноты. $L$ $\mathsf{NP}$ $\mathsf{NP}$ $\mathsf{P}\neq\mathsf{NP}$ $L$ $\mathsf{NP}$ $\mathsf{NP}=\mathsf{P}$

Относительно вопроса в названии, т. Е. «Должна ли -твердость быть конструктивной?». $\mathsf{NP}$

Ответ зависит от того, что мы подразумеваем под «конструктивным». Классически, проблема решения определяется как трудная, если $A$ $\mathsf{NP}$

\forall B \in N P B \leq_{m}^{P} A

$\forall B\in \mathsf{NP} \ B \leq^\mathsf{P}_m A$

что значит

\forall B \in N P \exists f \in F P \forall x \in {0, 1}^{*} (x \in B \leftrightarrow f (x) \in A)

$\forall B\in \mathsf{NP} \ \exists f\in\mathsf{FP} \ \forall x\in\{0,1\}^* \ (x\in B \leftrightarrow f(x)\in A)$

И по теореме Кука это эквивалентно

S A T \leq_{m}^{P} A

$SAT \leq^\mathsf{P}_m A$

что значит

\exists f \in F P \forall x \in {0, 1}^{*} (x \in S A T \leftrightarrow f (x) \in A)

$\exists f\in\mathsf{FP} \ \forall x\in\{0,1\}^* \ (x\in SAT \leftrightarrow f(x)\in A)$

$A$ $f$

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

Интуитивно мне кажется правдоподобным, что мы можем доказать такое утверждение, используя доказательство от противного и без какой-либо явной редукционной функции. Но это не будет означать, что нет конструктивного доказательства этого утверждения. Чтобы сказать больше, что никакого конструктивного доказательства не существует, мы должны быть более конкретными: доказательства в какой теории / системе? что мы подразумеваем под конструктивным доказательством?

Кава
источник

Зачем? Означает ли алгоритм P-времени для промежуточной задачи P = NP?

Мухаммед Аль-Туркистани

1

N P

$\mathsf{NP}$

P

$\mathsf{P}$

P \neq N P

$\mathsf{P}\neq\mathsf{NP}$

N P

$\mathsf{NP}$

12

$k$

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

[1] Джозеф Д. и Янг П. Некоторые замечания о функциях-свидетелях для неполиномиальных и неполных множеств в NP. Теоретическая информатика. том 39, стр. 225-237. 1985. Elsevier.

Samm
источник

6

Ниже приведен пример для вопроса в заголовке. Он взят из следующей статьи: Ян Краточвиль, Петр Савицкий и Жольт Туза. Еще одно вхождение переменных делает скачок выполнимости с тривиального на np-полный. SIAM Journal of Computing, 22 (1): 203–210, 1993.

Пусть f (k) будет максимальным целым числом r таким, что каждое k-SAT форум, в котором каждая переменная встречается не более r раз, выполнимо. Неизвестно, является ли f (k) вычислимым, хотя для него известны относительно жесткие границы (см. Х. Гебауэр, Р. Мозер, Д. Шедер и Э. Вельцль. Локальная лемма и удовлетворенность. Эффективные алгоритмы, стр. 30–54, 2009 г.).

(k, s) -SAT - это проблема k-SAT, ограниченная форумом, в котором каждая переменная встречается не более s раз.

Краточвил и соавт. доказано, что (k, f (k) +1) -SAT является NP-полной. Отметим, что задачи (k, f (k)) - SAT всегда выполнимы (по определению). Само сокращение неконструктивно: обратите внимание, что сокращение выводит формулу, в которой каждая переменная встречается не более f (k) +1 раз, даже если неизвестно, что f (k) вычислимо. Основная неконструктивная идея состоит в том, что, хотя значение f (k) неизвестно, существует формула (k, f (k) +1) -SAT, которая является неудовлетворительной, и они манипулируют этой формулой в соответствии со своими потребностями. ,

Или Саттат
источник

2

k

$k$

k

$k$

f (k)

$f(k)$

1

@Kaveh Действительно, сокращение не вычислимо, но сама проблема такова: (k, s) -SAT явно в NP для каждого s. Параметр, который делает задачу NP-полной, а именно f (k) +1, является объектом, который нельзя вычислить.

Или Sattath

2

Агравал и Бисвас представили NP-полный язык, для которого нет известного сокращения Карпа или Кука. Доказательство полноты следует потому, что его отношение-свидетель является универсальным (отношение-свидетель имеет требуемые операторы соединения и эквивалентности, которые должны быть универсальными). Язык приведен в разделе 6.3 в ссылке.

М. Агравал, С. Бисвас, Универсальные отношения в трудах IEEE Conferenceon Структура в теории сложности (1992), с. 207–220.

Мухаммед Аль-Туркистани
источник

1

NP-полный язык, по определению, является полным при сокращениях Карпа, так что означает первое предложение?

Эмиль Йержабек

@ EmilJeřábek Это означает именно то, что он говорит, нет никакого известного сокращения Карпа или Кука. Агравал и Бисвас доказали, что множества с универсальными отношениями NP-полны. Я предлагаю вам прочитать газету.

Мухаммед Аль-Туркистани

1

Нет, это не может означать, что он говорит, потому что то, что он говорит, не имеет смысла. Что-то, о чём не известно, что оно является полным при сокращении Карпа, тем более не известно, что оно является NP-полным. Я пролистал реферат и введение в статью и все еще не нашел ничего подходящего вашему описанию.

Эмиль Йержабек

@ EmilJeřábek Внимательно прочитайте раздел 6.3. Я боюсь, что скимминга недостаточно в этом случае :)

Мухаммед Аль-Туркистани

1

@ MohammadAl-Turkistany, я считаю, что дело в том, что утверждения «неизвестно, что они являются полными при сокращениях K.» и «нет известных сокращений K.» имеют разные значения. В посте сказано одно, а в вашем комментарии - другое.

Усул

Должна ли NP-полнота / твердость быть конструктивной?

Ответы: