Comment puis-je montrer qu'un problème Gap-P est en dehors de #P

14

Il existe un certain nombre de problèmes dans la théorie de la représentation combinatoire et la géométrie algébrique pour lesquels aucune formule positive n'est connue. Il y a plusieurs exemples auxquels je pense, mais permettez-moi de prendre le calcul des coefficients Kronecker comme exemple. Habituellement, la notion de "formule positive" n'est pas définie avec précision en combinatoire, mais elle signifie à peu près "une description comme la cardinalité d'un ensemble raisonnablement explicite". Récemment, j'ai parlé à Jonah Blasiak, et il m'a convaincu que la bonne définition de "formule positive" est #P . Je vais supposer que, sur ce site, je n'ai pas besoin de définir #P.

Buergisser et Ikenmeyer montrent que les coefficients de Kronecker sont durs #P. (Ils sont également toujours positifs, car ce sont des multiplicités de produits tensoriels.) Mais je suis raisonnablement sûr que personne ne connaît un moyen de les calculer qui les fait même entrer dans #P.

Supposons donc que je devais réellement essayer de prouver que les coefficients de Kronecker ne sont pas dans #P. Je suppose que ce que je ferais serait de supposer une certaine conjecture théorique de complexité, puis de réduire le produit Kronecker à un autre problème connu pour être complet pour une classe plus grande que #P.

Quelle conjecture pourrais-je supposer et à quel problème pourrais-je essayer de me réduire?

AJOUTÉ: Comme cela a été souligné dans les commentaires, Buergisser et Ikenmeyer montrent que les coefficients de Kronecker sont dans Gap-P, qui est assez proche de #P. Il semble donc que les questions que je devrais poser sont (1) Quels sont les problèmes de Gap-P-complet que je pourrais vraisemblablement réduire et (2) quelles sont les perspectives de montrer que Gap-P n'est pas #P? Je suppose que (2) devrait se diviser en deux parties (2a) les experts pensent-ils que ces classes sont différentes? et (2b) existe-t-il des stratégies probables pour le prouver?

J'espère que cette retouche de la question ne sera pas désapprouvée.

cc.complexity-theory counting-complexity lower-bounds David E Speyer
la source
5
Bienvenue sur cstheory! (J'ai ajouté la complexité de comptage et les limites inférieures à la question).
Kaveh
3
@Kaveh Bürgisser et Ikenmeyer montrent que le calcul des coefficients Kronecker est dans GapP. David, les coefficients de Kronecker sont-ils toujours des entiers non négatifs?
Tyson Williams,
2
Oui. Ce sont des multiplicites de produits tenseurs, ils sont donc toujours non négatifs.
David E Speyer
1
Vous avez un problème dans GapP et vous voulez prouver qu'il est en dehors de #P. Une approche évidente consiste à montrer que le problème est GapP-complet sous réductibilité fonctionnelle (Levin), ce qui impliquera que le problème est en dehors de #P en supposant # P ≠ GapP.
Tsuyoshi Ito
1
Ce que j'ai écrit dans mon commentaire précédent est incorrect, car tout problème dans GapP est fonctionnel réductible à #P (si je ne me trompe pas cette fois). En d'autres termes, la différence entre #P et GapP est trop délicate à gérer en utilisant la réductibilité fonctionnelle.
Tsuyoshi Ito

Réponses:

12

Je suggérerais de regarder les propriétés des fonctions #P qui sont différentes des fonctions Gap-P. Par exemple, déterminer si une fonction #P est nulle est en co-NP. Si vous pouviez montrer que déterminer si les coefficients de Kronecker sont nuls est UP-hard, alors vous auriez "Coefficients de Kronecker en #P implique UP en co-NP", une conclusion peu probable.

Lance Fortnow
la source
3

GapP est exactement la fermeture de #P sous soustraction. D'un autre côté, #P n'est pas fermé par soustraction à moins que UP = PP. Je crois que cela répond à vos questions.

Tayfun Pay
la source
4
Si vous avez voté contre, expliquez au moins pourquoi c'est mal .. Merci
Tayfun Payez le
3
Je suis d'accord. Pour autant que je sache, la réponse fait deux déclarations correctes et répond à la question d'origine (bien que ma recherche ait révélé que UP = PH est le conditionnel souhaité?)
Suresh Venkat
2
@Suresh: Comment ce message répond-il à la question d'origine? La question ne concerne pas un problème GapP-complete.
Tsuyoshi Ito
3
la partie (2) de la mise à jour demande: "quelles sont les chances que GapP ne soit pas égal à #P". cette réponse souligne qu'à moins qu'un effondrement ne se produise, #P n'est pas fermé par soustraction et donc il n'y a même aucun intérêt à parler d'égalité.
Suresh Venkat
1
@Suresh: Ceci est le papier. M.Ogiwara & L. Hemachandra. "Une théorie de la complexité pour les propriétés de fermeture réalisables." Journal of Computer and System Sciences Volume 46 Pages 295-325. 1993.
Tayfun Pay du
0

La question du calcul des caractères des représentations irréductibles du groupe symétrique pourrait être un candidat naturel.

Je pense que Charles Hepler montre que c'est Gap-P complet, mais je ne suis pas sûr: pour un lien vers sa thèse de maîtrise, voir https://dspace.ucalgary.ca/handle/1880/45530?mode=full

Hari
la source