Problem NP-zupełny z wielomianowo wieloma certyfikatami?

Nazwijmy język NP słabo certyfikowany, jeśli i tylko jeśli: $L \in$

Istnieje wielomian taki, że dla każdego wejścia o rozmiarze , jeśli to zestaw certyfikatów który weryfikuje, że ma wielkość wielomianową, tj. . $p : \mathbb{N} \rightarrow \mathbb{N}$ $x \in \Sigma^*$ $n$ $x \in L$ $U_x$ $u$ $x \in L$ $|U_x| \leq p(n)$

W krótszych względem każdy wejściowy jest na większej wysokości wielomianu certyfikatów weryfikujących jej włączenie . $x$ $L$

Przykład: Aby to zilustrować, rozważ problem : $\mathbf{CLIQUE}$

$\mathbf{CLIQUE} = \{\; (G,k) \;\mid\; G \text{ has a clique of size } k \;\}$

Język jest nie słabo certyfikat jako wejścia z łatwością może mieć wykładniczy ilość -cliques działającego w odcinkach, które dowodzą, że . $\mathbf{CLIQUE}$ $x = (G,k)$ $k$ $x \in \mathbf{CLIQUE}$

Przykład zakończenia

Pytanie brzmi zatem: czy są jakieś znane słabo certyfikowane języki NP-complete? Wszelkie spostrzeżenia są mile widziane, nawet jeśli nie odpowiadają na pytanie!

Uwaga : ta definicja różni się od definicji rzadkiego języka!

cc.complexity-theory complexity-classes gdiazc
źródło

Z pewnością rozumiem, czy to prawda?

jest technicznie zdefiniowane w odniesieniu do określonego weryfikatora

, to znaczy dla

. A

jest „słabo certyfikowany” wtedy i tylko wtedy, gdy istnieje weryfikator

dla

taki, że jego

spełniają warunek wielkości wielomianowej.

U_{x}

$U_x$

V

$V$

x \in L

$x \in L$

U_{x} = {u : V (x, u) = 1}

$U_x = \{u : V(x,u) = 1\}$

L

$L$

V

$V$

L

$L$

U_{x}

$U_x$

usul

Odpowiedzi:

Nie, nie jest znany słabo poświadczone językach -Complete. Klasa, która opisujesz jest znany jako . Uważa się, że , więc nie -Complete problem jest znany w fewP. (Jest to niemożliwe, chyba że ). $NP$ $fewP$ $fewP \ne NP$ $NP$ $fewP=NP$

Mohammad Al-Turkistany
źródło

Właśnie tego szukałem. Twoje zdrowie!

gdiazc

Znalazłem odniesienia do kilkuP (w zoo złożoności), ale czy zdarzyło ci się mieć odniesienie na poparcie stwierdzenia: „powszechnie uważa się, że małoP

NP”? Na przykład, czy kilka

NP implikuje

czy coś w tym rodzaju?

\neq

$\neq$

=

$=$

P = N P

$P = NP$

gdiazc

F e w P

$\mathsf{FewP}$

F e w

$\mathsf{Few}$

F e w

$\mathsf{Few}$

x \in L

$x \in L$

Q (x, | U_{x} |)

$Q(x, |U_x|)$

x \in L

$x \in L$

F e w P

$\mathsf{FewP}$

F e w

$\mathsf{Few}$

F e w P

$\mathsf{FewP}$

U P

$\mathsf{UP}$

B P P

$\mathsf{BPP}$

F e w

$\mathsf{Few}$

F e w P

$\mathsf{FewP}$

P r o m i s e F e w

$\mathsf{PromiseFew}$

P r o m i s e F e w P

$\mathsf{PromiseFewP}$

F e w

${\bf Few}$

F e w P

${\bf FewP}$

L

$L$

F e w P

${\bf FewP}$

F e w P

${\bf FewP}$

Tayfun Zapłać