Problemas sucintos en

El estudio de la representación sucinta de gráficos fue iniciado por Galperin y Wigderson en un artículo de 1983, donde demuestran que para muchos problemas simples como encontrar un triángulo en un gráfico, la versión sucinta correspondiente en -completa. Papadimitriou y Yanakkakis amplían esta línea de investigación, y demuestran que para un problema que es -complete / -complete, la versión correspondiente de Succinct, concretamente Succinct es respectivamente, -complete y -complete. (También muestran que si es Π N P P Π N E X P E X P Π N L Π P S P A C $\mathsf{NP}$$\Pi$$\mathsf{NP}$$\mathsf{P}$$\Pi$$\mathsf{NEXP}$$\mathsf{EXP}$$\Pi$$\mathsf{NL}$-completo, entonces Succinct es -completo.$\Pi$$\mathsf{PSPACE}$

Ahora mi pregunta es, ¿hay algún problema conocido por para el cual, la versión sucinta correspondiente está en ? Me interesaría saber acerca de otros resultados relacionados (tanto positivos como imposibles, si los hay) que podría haber pasado por alto. (No pude localizar nada de interés mediante una búsqueda en Google, ya que las palabras de búsqueda como sucinta, representación, problemas, gráficos conducen a casi cualquier resultado de complejidad :))$\Pi$$\mathsf{P}$

Aquí hay un problema interesante cuya versión sucinta tiene propiedades interesantes. Definir Circuit-Size- como el problema: dada una función booleana como una cadena de bits, ¿esta función tiene un circuito de tamaño como máximo ? Tenga en cuenta que este problema está en .2 n 2 n / 2 N $2^{n/2}$$2^n$$2^{n/2}$$NP$

Una forma de definir Succinct-Circuit-Size- sería: para una constante , dada una , tamaño de circuito , queremos saber si su tabla de verdad es una instancia de Tamaño de circuito- . Pero este es un problema trivial: todas las entradas que son circuitos reales son instancias de sí. Por lo que este problema está en . k n n k C 2 n / 2$2^{n/2}$$k$$n$$n^k$$C$$2^{n/2}$$P$

Una forma más general de definir Succinct-Circuit-Size- sería: se nos da un circuito arbitrario C y queremos saber si su tabla de verdad codifica una instancia de Circuit-Size- 2 n / 2 . Pero si n es el número de entradas a C , m es el tamaño de C , y m ≤ 2 n / 2 , podemos aceptar de forma automática: la entrada en sí es un testigo de la lengua. De lo contrario, tenemos m ≥ 2 n / 2 . En ese caso, la longitud de entrada $2^{n/2}$$C$$2^{n/2}$$n$$C$$m$$C$$m \leq 2^{n/2}$$m \geq 2^{n/2}$$m$ya es enorme, por lo que podemos tratar todos los posibles asignaciones en m O ( 1 ) tiempo, obtenemos la tabla de verdad de la función, y ahora estamos de vuelta a la original N P problema de nuevo. Así que este es un problema en N P cuya versión sucinta también está en N P .$2^n$$m^{O(1)}$$NP$$NP$$NP$

Se cree que este problema no es -hard; ver el artículo de Kabanets y Cai (http://www.cs.sfu.ca/~kabanets/Research/circuit.html)$NP$

Dado que incluso decidir si el gráfico representado por una representación sucinta dada contiene al menos un borde o no es equivalente al Circuito SAT y, por lo tanto, NP completo, es tentador afirmar que cualquier propiedad interesante de una representación sucinta debe ser NP-dura bajo una definición adecuada de "interesante". Esta afirmación sería un análogo teórico de la complejidad para el teorema de Rice . Por desgracia, encontrar el análogo teórico de la complejidad más general del teorema de Rice es un problema abierto , aunque hay resultados que dan algunas formas de tales análogos teóricos de la complejidad.

No quise que esto fuera una respuesta, pero requeriría demasiados comentarios. Espero que sea útil.

$\Pi$$\Pi$$2^n$$2^n/x$$x = n^{O(1)}$

$\Pi$$s$$\Pi$$s$$\Pi$

$\Pi$