Известен ли размер свидетельства для каждого языка NP, уже известного?

Вопрос возник у меня, когда я получил ответ Даны Мошковиц на другую тему .

Пусть будет языком NP , и пусть будет соответствующим отношением NP . Мы знаем, что существует некоторый полином такой, что: $L$ $R_L$ $p$

$\forall x \in L, \\, \exists w \in \\{0,1\\}^{p(|x|)} \quad (x,w) \in R_L$

Вышеприведенное утверждение требует только наличия такого , но не требует его явного определения . Напротив, для каждого языка NP, который я знаю, уже известен: $p$ $p$

Для SAT размер свидетеля равен числу атомов, фигурирующих в формуле.
Для гамильтоничности размер свидетеля равен , где - множество вершин. $O(|V|)$ $V$
Для графа 3-раскраски размер свидетеля равен , где - множество вершин. $O(|V|)$ $V$

Существует ли язык NP (даже искусственный), для которого мы знаем, что существует некоторый полином ограничивающий размер свидетеля, но мы не можем явно определить ? $p$ $p$

cc.complexity-theory np М.С. Дусти
источник

Для любого данного языка в NP есть много отношений NP, которые вызывают его. Вы спрашиваете о языках

где минимальный многочлен

неизвестен (то есть, где мы можем попытаться минимизировать многочлен, рассматривая различные отношения, порождающие один и тот же

), или об отношениях, где соответствующий многочлен

неизвестен (но мы знаем, что существует)?

L

$L$

p

$p$

L

$L$

p

$p$

Джошуа Грохов

@ Джошуа: Я мог бы неправильно понять ваш комментарий, но если мы знаем минимальное

по всем отношениям для некоторой NP-полной задачи и если оно ненулевое, разве это не означает

p

$p$

P \neq N P

$P\neq NP$

Конг Хан

o (n)

$o(n)$

N E X P ⊈ P / p o l y

$NEXP \not\subseteq P/poly$

@ Джошуа: Да, конечно! Понял, спасибо.

Конг Хан

Если для Circuit SAT существует отношение с размером свидетеля , где - количество входов в цепь, а - размер схемы, тогда да, ,

k - ω (\log n)

$k-\omega(\log n)$

k

$k$

n

$n$

N E X P ⊈ P / p o l y

$NEXP \not\subseteq P/poly$

Райан Уильямс

Ответы:

Если вы не возражаете против искусственных языков, мы можем построить такие проблемы, используя практически любое число k, значение которого неизвестно математикам. Например, нам неизвестно значение R (5,5) (пятое число Рамсея ) или размер наибольшего исключенного минора из семейства безузловых графов (это число конечно из -за теоремы Робертсона-Сеймура ) или значение BB (10), где BB () обозначает функцию Busy Beaver . Пусть k равно любому из этих чисел. Мы знаем, что k конечно, но мы не знаем значение k.

Теперь построим некоторую задачу в NP, где свидетель имеет размер . Сверху головы я не могу придумать хороший способ сделать это, но вот один из способов. Пусть вход будет кратким описанием графа. Поскольку размер описания равен n, граф имеет экспоненциально много вершин. (Например, возможно, вход является схемой, которая принимает два входа x и y и сообщает вам, является ли (x, y) ребром в графе.) Вопрос состоит в том, чтобы определить, содержит ли граф путь длины . Эта проблема в NP, потому что проверяющий может отправить список вершин на пути в порядке, который может проверить верификатор. Размер свидетеля . $O(n^k)$ $n^k$ $n^k$

Робин Котари
источник