Idiomas

12

¿Qué otros ~~problemas de~~ idiomas diferentes al isomorfismo de gráficos hay en ? ¿Puedes dar algunas referencias? $NP\cap coAM$

Actualización: Olvidé mencionar que estoy interesado en idiomas que no se sabe que están en . $coNP$

cc.complexity-theory reference-request complexity-classes graph-isomorphism Marcos Villagra
fuente

Quieres decir que no se sabe que están en , ¿verdad?

c o N P

$\mathrm{coNP}$

ilyaraz

sí, olvidé mencionar eso

Marcos Villagra

Pero se cree que , por lo que la mejor manera de formular la pregunta es reemplazar lo creído por lo conocido. Perdón por mi pedantismo.

c o N P = c o A M

$\mathrm{coNP} = \mathrm{coAM}$

ilyaraz

10

Los únicos otros que conozco también son problemas de isomorfismo: isomorfismo grupal e isomorfismo en anillo. Los protocolos para ambos son esencialmente los mismos que para el isomorfismo gráfico. $coAM$

El isomorfismo grupal se reduce a isomorfismo gráfico y se reduce a isomorfismo en anillo.

Curiosamente, a diferencia de (lo que se conoce por) grupos y gráficos, para los anillos, determinar si un anillo tiene un automorfismo no trivial está en , mientras que encontrar un automorfismo no trivial es equivalente a factorizar números enteros. Ver Neeraj Kayal, Nitin Saxena. Complejidad de los problemas del anillo de morfismo. Complejidad computacional 15 (4): 342-390 (2006) . $P$

Joshua Grochow
fuente

9

Otro problema es encontrar soluciones aproximadas al problema de vector más corto o más cercano (SVP, CVP). Por ejemplo, se ha demostrado (por Goldreich y Goldwasser, 1998 ) que la aproximación de SVP dentro de un factor de está en , donde denota la dimensión de la enrejado. No se sabe si este problema está en . $O(\sqrt{n/\log(n)})$ $NP \cap coAM$ $n$ $coNP$

Por otro lado, también se sabe (ver Aharonov y Regev, 2004 ) que encontrar soluciones aproximadas está en . $O(\sqrt{n})$ $NP \cap coNP$

MRA
fuente

2

Estos son problemas de búsqueda, no problemas de decisión, y las variantes de decisión de los problemas de aproximación son problemas prometedores. Andy Drucker y yo tuvimos una discusión similar sobre SVP y CVP en cstheory.stackexchange.com/questions/330/… "

Joshua Grochow el

6

Bueno, sé que , y todos los idiomas que poseen pruebas estadísticas de conocimiento cero caen en . Simbólicamente, . (Donde es la clase de idiomas que admite conocimiento cero perfecto, y es la clase de idiomas que admite conocimiento cero estadístico). Vea los siguientes enlaces para la prueba: $\mathbf{NP}\subseteq\mathbf{AM}$ $\mathbf{AM}\cap\mathbf{coAM}$ $\mathbf{PZK}\subseteq \mathbf{SZK}\subseteq \mathbf{AM}\cap\mathbf{coAM}$ $\mathbf{PZK}$ $\mathbf{SZK}$

La complejidad del conocimiento cero perfecto

Los lenguajes estadísticos de conocimiento cero se pueden reconocer en dos rondas

Los lenguajes como el problema de vector más corto o más cercano (SVP, CVP) caen en (ver el documento de Goldreich y Goldwasser, citado anteriormente). $\mathbf{SZK}$

MS Dousti
fuente

Idiomas

Respuestas: