vs

15

Dans nos travaux récents, nous résolvons un problème de calcul qui s'est posé dans un contexte combinatoire, en supposant que , oùEXPEXP est la version E X P deEXPEXP . Le seul papier surP que nous avons trouvé était le document Beigel-Buhrman-Fortnow1998cité surComplexity Zoo. Nous comprenons que nous pouvons prendre des versions à parité desproblèmes N E X P -complets (voircette question), mais peut-être que beaucoup d'entre eux ne sont en fait pas complets enEXPNEXP . EXP

QUESTION: Y a-t-il des raisons de complexité de croire que ? Existe-t-il des problèmes combinatoires naturels qui sont complets enEXPEXP ? Y a-t-il des références qui pourraient nous manquer? EXP

Igor Pak
la source
6
Je pense que les versions de parité d'au moins certains problèmes NEXP-complets seraient complete-complets pour la même raison, par exemple SUCCINCT 3SAT. Les classes de parité sont «syntaxiques» tout comme le non-déterminisme existentiel, vous avez donc les mêmes méthodes standard pour créer des problèmes complets.
Greg Kuperberg
Merci, Greg. Je comprends. Cependant, tous les problèmes ne fonctionneront pas, par exemple, la parité du nombre de 3 couleurs des graphiques SUCCINCT est facile.
Igor Pak
2
Le problème dans votre exemple de la parité du nombre de 3 coloris (qui bien sûr est divisible par 6) est orthogonal à la question posée des classes de complexité de niveau EXP. La question est de savoir s'il y a une réduction parcimonieuse, c'est-à-dire une réduction qui préserve le nombre de témoins. C'est souvent connu, mais parfois non. Par exemple, dans le cas des 3 couleurs, il y a un beau papier de Barbanchon (que j'ai récemment vu pour mes propres raisons) qui donne une réduction parcimonieuse de SAT, sauf pour le facteur 6.
Greg Kuperberg
2
Ah, c'est vrai. Intéressant. Je l'ai trouvé: Régis Barbanchon, Sur un graphique unique 3-colorabilité et réductions parcimonieuses dans l'avion (2004).
Igor Pak
3
@GregKuperberg: On dirait une réponse! Notez que Valiant a montré ( people.seas.harvard.edu/~valiant/focs06.pdf ) que même est P -complete. 2SATP
Joshua Grochow

Réponses:

14

En termes de raisons de complexité (plutôt que des problèmes complets): Le Hartmanis-Immerman-Sewelson Théorème devrait également fonctionner dans ce contexte, à savoir: ssi il existe un ensemble polynomiale clairsemée dans PP . Étant donné la distance à laquelle nous pensons que P et P sont - par exemple, Toda a montré que P HB P P P - il serait assez surprenant s'il n'y avait pas d'ensembles clairsemés dans leur différence.EXPEXPPPPPPHBPPP

Plus directement, s'il n'y avait pas d'ensembles clairsemés dans leur différence, cela dirait que pour chaque vérificateur , si le nombre de chaînes de longueur n avec un nombre impair de témoins est limité par n O ( 1 ) , alors le problème [ de dire s'il y a un nombre impair de témoins] doit être en P . Cela semble être un fait assez frappant et peu probable.NPnnO(1)P

Joshua Grochow
la source
Je ne comprends pas la dernière partie. Tout problème NP peut être exprimé de telle manière que le nombre de témoins soit toujours pair, et 0 est sûrement borné polynomialement, donc vous dites effectivement que P = NP, et je ne vois pas comment cela va suivre.
Emil Jeřábek soutient Monica
1
@Emil, le "vérificateur" entre parenthèses semble clarifier ce que Josh voulait dire.
Kaveh
@ EmilJeřábek: En effet, Kaveh l'a compris exactement. Comme vous le faites remarquer, la déclaration ne fonctionne vraiment que si vous parlez de chaque vérificateur NP, plutôt que de chaque problème NP. J'ai modifié la réponse pour que ce ne soit plus un commentaire entre parenthèses.
Joshua Grochow
Désolé, mais cela n'a rien clarifié. Si la déclaration s'applique à tous les vérificateurs, elle s'applique en particulier aux vérificateurs qui ont toujours un nombre pair de témoins.
Emil Jeřábek soutient Monica
1
@ EmilJeřábek: Ah, oui, je vois votre confusion maintenant (je pense). Clarifié. Le résultat me semble un peu moins frappant, mais pas beaucoup (surtout à la lumière du résultat de Toda).
Joshua Grochow