¿Cómo puedo mostrar que un problema de Gap-P está fuera de #P

14

Existen varios problemas en la teoría de representación combinatoria y la geometría algebraica para los cuales no se conoce una fórmula positiva. Estoy pensando en varios ejemplos, pero permítanme tomar los coeficientes de cálculo de Kronecker como mi ejemplo. Por lo general, la noción de "fórmula positiva" no se define con precisión en la combinatoria, pero significa "una descripción como la cardinalidad de un conjunto razonablemente explícito". Recientemente, he estado hablando con Jonah Blasiak, y me ha estado convenciendo de que la definición correcta de "fórmula positiva" es #P . Asumiré que, en este sitio, no necesito definir #P.

Buergisser e Ikenmeyer muestran que los coeficientes de Kronecker son #P difíciles. (También son siempre positivos, porque son multiplicidades de productos tensoriales). Pero estoy razonablemente seguro de que nadie conoce una forma de calcularlos que incluso los coloque en #P.

Entonces, supongamos que realmente intentara probar que los coeficientes de Kronecker no están en #P. Supongo que lo que haría es asumir alguna conjetura teórica de complejidad y luego reducir el producto Kronecker a otro problema que se sabe que está completo para una clase mayor que #P.

¿Qué conjetura podría asumir y a qué problema podría intentar reducir?

AGREGADO: Como se ha señalado en los comentarios, Buergisser e Ikenmeyer muestran que los coeficientes de Kronecker están en Gap-P, que está bastante cerca de #P. Entonces, parece que las preguntas que debería hacer son: (1) ¿Cuáles son algunos problemas de Gap-P-complete que podría reducir y (2) cuáles son las perspectivas de demostrar que Gap-P no es #P? Supongo que (2) debería dividirse en dos partes (2a) ¿Los expertos creen que estas clases son diferentes? y (2b) ¿existen estrategias probables para probarlo?

Espero que esta edición de la pregunta no esté mal vista.

cc.complexity-theory counting-complexity lower-bounds David E Speyer
fuente
55
Bienvenido a cstheory! ( Agregué complejidad de conteo y límites inferiores a la pregunta).
Kaveh
3
@Kaveh Bürgisser e Ikenmeyer muestran que calcular los coeficientes de Kronecker está en GapP. David, ¿los coeficientes de Kronecker son siempre enteros no negativos?
Tyson Williams
2
Si. Son multiplicitas de productos tensoriales, por lo que siempre son no negativos.
David E Speyer
1
Tiene un problema en GapP y quiere demostrar que está fuera de #P. Un enfoque obvio es mostrar que el problema es GapP completo bajo la capacidad de reducción funcional (Levin), lo que implicará que el problema está fuera de #P suponiendo # P ≠ GapP.
Tsuyoshi Ito
1
Lo que escribí en mi comentario anterior es incorrecto, porque cualquier problema en GapP es funcionalmente reducible a #P (si no me equivoco esta vez). En otras palabras, la diferencia entre #P y GapP es demasiado delicada para manejarla usando la reducibilidad funcional.
Tsuyoshi Ito

Respuestas:

12

Sugeriría mirar las propiedades de las funciones #P que son diferentes de las funciones Gap-P. Por ejemplo, determinar si una función #P es cero está en co-NP. Si pudieras mostrar que determinar si los coeficientes de Kronecker son cero es UP-hard, entonces tendrías "coeficientes de Kronecker en #P implica UP en co-NP", una conclusión poco probable.

Lance Fortnow
fuente
3

GapP es exactamente el cierre de #P bajo resta. Por otro lado, #P no se cierra bajo sustracción a menos que UP = PP. Creo que eso responde sus preguntas.

Tayfun Pay
fuente
44
Si lo rechazó, al menos explique por qué está mal. Gracias
Tayfun Pay
3
Estoy de acuerdo. Por lo que puedo decir, la respuesta hace dos afirmaciones correctas y responde la pregunta original (aunque mi búsqueda reveló que UP = PH es el condicional deseado)
Suresh Venkat
2
@Suresh: ¿Cómo responde esta publicación a la pregunta original? La pregunta no es sobre un problema completo de GapP.
Tsuyoshi Ito
3
la parte (2) en la actualización pregunta: "¿cuáles son las perspectivas de que GapP no sea igual a #P". Esta respuesta señala que, a menos que ocurra un colapso, #P no se cierra por resta y, por lo tanto, no tiene sentido hablar de igualdad.
Suresh Venkat
1
@Suresh: Este es el periódico. M.Ogiwara y L. Hemachandra. "Una teoría de la complejidad para propiedades de cierre factibles". Revista de Ciencias de Computadoras y Sistemas Volumen 46 Páginas 295-325. 1993.
Tayfun paga el
0

La cuestión de calcular caracteres de representaciones irreducibles del grupo simétrico podría ser un candidato natural.

Creo que Charles Hepler muestra que está completo Gap-P, pero no estoy seguro: para un enlace a su tesis de maestría, consulte https://dspace.ucalgary.ca/handle/1880/45530?mode=full

Hari
fuente