Existem vários problemas na teoria da representação combinatória e na geometria algébrica para os quais nenhuma fórmula positiva é conhecida. Existem vários exemplos em que estou pensando, mas deixe-me tomar como exemplo o coeficiente de computação Kronecker . Normalmente, a noção de "fórmula positiva" não é definida precisamente na combinatória, mas significa aproximadamente "uma descrição como a cardinalidade de um conjunto razoavelmente explícito". Recentemente, conversei com Jonah Blasiak, e ele me convenceu de que a definição correta de "fórmula positiva" é #P . Vou assumir que, neste site, não preciso definir #P.
Buergisser e Ikenmeyer mostram que os coeficientes de Kronecker são #P difíceis. (Eles também são sempre positivos, porque são multiplicidades de produtos tensores.) Mas estou razoavelmente certo de que ninguém conhece uma maneira de calculá-los que os coloca no #P.
Então, suponha que eu realmente tentei provar que os coeficientes do Kronecker não estão no #P. Suponho que o que eu faria seria assumir algumas conjecturas teóricas da complexidade e, em seguida, reduzir o produto Kronecker a outro problema que se sabe estar completo para uma classe maior que #P.
Que conjectura posso assumir e a que problema devo tentar reduzir?
ADICIONADO: Como foi apontado nos comentários, Buergisser e Ikenmeyer mostram que os coeficientes Kronecker estão no Gap-P, que é bem próximo do #P. Portanto, parece que as perguntas que eu deveria fazer são: (1) Quais são alguns dos problemas completos do Gap-P que eu poderia reduzir de forma plausível e (2) quais são as perspectivas de mostrar que o Gap-P não é #P? Eu acho que (2) deve ser dividido em duas partes (2a): os especialistas acreditam que essas classes são diferentes? e (2b) existem estratégias prováveis para provar isso?
Espero que essa edição da pergunta não seja desaprovada.
fonte
Respostas:
Eu sugiro olhar para propriedades das funções #P que são diferentes das funções Gap-P. Por exemplo, determinar se uma função #P é zero está em co-NP. Se você pudesse mostrar que determinar se os coeficientes de Kronecker é zero é UP-hard, então você teria "Coeficientes de Kronecker em #P implica UP em co-NP", uma conclusão improvável.
fonte
GapP é exatamente o fechamento do #P sob subtração. Por outro lado, #P não é fechado em subtração, a menos que UP = PP. Eu acredito que responde às suas perguntas.
fonte
A questão da computação Personagens de representações irredutíveis do grupo simétrico podem ser um candidato natural.
Acho que Charles Hepler mostra que o Gap-P está completo, mas não tenho certeza: para um link para a sua tese de mestrado, consulte https://dspace.ucalgary.ca/handle/1880/45530?mode=full
fonte