NP-problema completo con polinomios muchos certificados?

Llamemos un idioma NP escasamente certificado si y solo si: $L \in$

Existe un polinomio tal que para cada entrada de tamaño , si entonces el conjunto de certificados que verifican que tiene un tamaño polinómico, es decir . $p : \mathbb{N} \rightarrow \mathbb{N}$ $x \in \Sigma^*$ $n$ $x \in L$ $U_x$ $u$ $x \in L$ $|U_x| \leq p(n)$

En términos más cortos, cada entrada tiene en una cantidad más polinomio de certificados que verifican su inclusión en . $x$ $L$

Ejemplo: para ilustrar, considere el problema : $\mathbf{CLIQUE}$

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

El lenguaje no está escasamente certificado , ya que una entrada podría tener fácilmente una cantidad exponencial de cliques que actúan como certificados que prueban que . $\mathbf{CLIQUE}$ $x = (G,k)$ $k$ $x \in \mathbf{CLIQUE}$

Fin de ejemplo

La pregunta, entonces, es: ¿hay algún lenguaje NP completo completo escasamente certificado? Cualquier idea es bienvenida, ¡incluso si no responden la pregunta!

Nota : ¡esta definición es diferente de la de un lenguaje escaso!

cc.complexity-theory complexity-classes gdiazc
fuente

Para estar seguro de entender, ¿es esto correcto? se define técnicamente con respecto a algún verificador particular , es decir, para , . Y está "escasamente certificado" si y solo si existe un verificador para modo que sus s satisfagan la condición de tamaño polinómico.

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

Respuestas:

No, no se conocen idiomas completos escasamente certificados . La clase que está describiendo se conoce como . Se cree ampliamente que , por lo tanto, no se sabe que el problema completo de esté en pocosP. (Es imposible a menos que ). $NP$ $fewP$ $fewP \ne NP$ $NP$ $fewP=NP$

Mohammad Al-Turkistany
fuente

Esto es exactamente lo que estaba buscando. ¡Salud!

gdiazc

He encontrado referencias para fewP (en el Complexity Zoo), pero ¿tendría una referencia para apoyar la afirmación: "se cree ampliamente que fewP NP"? Por ejemplo, ¿P NP implicaría o algo por el estilo?

\neq

$\neq$

=

$=$

P = N P

$P = NP$

gdiazc

@TayfunPay: Estoy bastante seguro de que está hablando de y no de . es más general: requiere, como máximo, polinomialmente que los certificados sean aceptados por el verificador, pero si o no no está determinado por si existe un certificado aceptado por el verificador, sino más bien un predicado adicional . El OQ parece tener la intención de preguntar dónde la existencia de cualquier certificado implica , que es exactamente .

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}$

Joshua Grochow

@TayfunPay: Por lo que yo entiendo, y son ambas clases semánticas, al igual que o . En particular, lo que dices es incorrecto. , al igual que , requiere que el número de rutas de aceptación del verificador esté limitado por un polinomio en todas las entradas. (Lo que es algo como o ...) Ver Def. 1.2 de Cai y Hemachandra: dx.doi.org/10.1007/BFb0028987

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}$

Joshua Grochow

@JoshuaGrochow Acabo de tener la oportunidad de revisarlo. Tienes razón, es de hecho una clase semántica. Pensé que era la versión sintáctica de . OK Sin embargo, todavía creo que el cuestionario preguntaba por el tipo de escenario "si y solo si" Debido a que un lenguaje dado está en "if", el número total de rutas de aceptación están delimitadas por un polinomio y "not" en si no hay rutas de aceptación. Por lo tanto, NO sabemos qué sucede cuando el número de rutas de aceptación son exponenciales porque no es "si y solo si" ...

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 paga el