NP-полная проблема с полиномиальным количеством сертификатов?

10

Давайте назовем язык NP редко сертифицированным тогда и только тогда, когда:L∈

Существует такой многочлен , что для каждого входа x ∈ Σ ∗ размера n , если x ∈ L, то множество U x сертификатов u, которые проверяют, что x ∈ L имеет полиномиальный размер, т. Е. | U x | ≤ p ( n ) .p:N→Nx∈Σ∗nx∈LUxux∈L|Ux|≤p(n)

В более коротких сроках, каждый входной имеют в большинстве полиномиального количества сертификатов , которые подтверждают его включение в L .xL

Пример: для иллюстрации рассмотрим задачу :CLIQUE

CLIQUE={(G,k)∣G has a clique of size k}

Язык является не разреженно сертифицирован , в качестве входных данных х = ( G , K ) может легко иметь экспоненциальное количество K -cliques , действующий как сертификаты , которые доказывают , что х ∈ C L I Q U E .CLIQUE x=(G,k)kx∈CLIQUE

Конец примера

Тогда возникает вопрос: существуют ли какие-либо известные NP-полные редко сертифицированные языки? Любые идеи приветствуются, даже если они не отвечают на вопрос!

Примечание : это определение отличается от определения разреженного языка!

cc.complexity-theory complexity-classes gdiazc
источник
Конечно, я понимаю, это правильно? технически определяются относительно некоторого конкретного верификатора V , то есть для Купить ∈ L , U х = { ¯u : V ( х , у ) = 1 } . И L "редко сертифицируется" тогда и только тогда, когда существует верификатор V для L , так что его U x s удовлетворяют условию полиномиального размера. UxVx∈LUx={u:V(x,u)=1}LVLUx
Усул

Ответы:

12

Нет, не существует известных редко сертифицированных -комплектных языков. Класс , который вы описываете, называется ф е ш Р . Широко распространено мнение о том , что е е ж P ≠ N P , Таким образом, нет N P -полным проблема , как известно, в fewP. (Это невозможно, если f e w P = N P ).NPfewPfewP≠NPNPfewP=NP

Мухаммед Аль-Туркистани
источник
Это именно то, что я искал. Ура!
gdiazc
Я нашел ссылки для немногих P (в Зоопарке Сложности), но у вас случайно не было ссылки, подтверждающей утверждение: «широко распространено мнение, что немногие P NP»? Например, мало ли P = NP подразумевает P = N P или что-то в этом роде? ≠=P=NP
gdiazc
1
@TayfunPay: я почти уверен, что он говорит о а не о F e w . F e w является более общим - он требует, чтобы в большинстве случаев верификаторы принимали сертификаты полиномиальным образом, но то, является ли x ∈ L или нет, определяется не тем, существует ли сертификат, принятый верификатором, а скорее дополнительным предикатом Q ( x , | U x | ) . OQ, похоже, намеревается спросить о том, где существование любого сертификата подразумевает x ∈ LFewPFewFewx∈LQ(x,|Ux|)x∈L, Что в точности . FewP
Джошуа Грохов
1
@TayfunPay: Насколько я понимаю, и F е ш Р являются оба семантических классов, так же , как U P или B P P . В частности, то, что вы говорите, неверно. F e w , как и F e w P , требует, чтобы число принимающих путей верификатора было ограничено полиномом на всех входах. (То, что вы определили, это что-то вроде P r o m i s e F e w или P rFewFewPUPBPPFewFewPPromiseFew ...) См Защиты. 1.2 из Cai &Hemachandra:dx.doi.org/10.1007/BFb0028987PromiseFewP
Джошуа
@JoshuaGrochow У меня только есть шанс просмотреть это. Вы правы, действительно семантический класс. Я подумал , что это синтаксический версия F е ш Р . ОК Тем не менее, я все еще считаю, что в анкете запрашивался сценарий типа «если и только если». Поскольку данный язык L находится в F e w P «если», общее число принимающих путей ограничено полиномом и «не» в F e w P, если нет принимающих путей. Таким образом, мы НЕ знаем, что происходит, когда число принимающих путей экспоненциально, потому что это не «тогда и только тогда» ....FewFewPLFewPFewP
Tayfun Pay