Quelle est la difficulté de la simulation exacte des algorithmes et d'une opération connexe sur les classes de complexité

17

Taquin

Étant donné que le problème est assez long, voici un cas spécial qui capture son essence.

Problème: Soit A un algorithme detrministique pour 3-SAT. Est le problème de la simulation complète de l'algorithme A (sur chaque instance du problème). P-Space dur?

(Plus précisément, y a-t-il des raisons de croire que cette tâche est difficile pour P-Space, est-ce que quelque chose dans ce sens découle des conjectures CC standard et espère-t-on prouver que cette tâche est difficile pour une classe de complexité X qui est présumée être strictement supérieur à NP.)

Questions connexes : problèmes -d'espace-complet-problèmes-intrinsèquement moins faciles à résoudre que-np-problèmes-complets ;

MISE À JOUR ÉDITÉE : Il existe différentes interprétations pour "Simuler complètement A". Et il peut y avoir différentes réponses intéressantes selon l'interprétation. (Ryan Williams a également proposé une interprétation pour simuler un algorithme non déterministe.) Pour une certaine façon d'associer un problème de décision à la tâche de calcul "Simuler complètement A", Joe Fitzsimons a trouvé un algorithme A pour lequel ce problème de décision associé est toujours dans NP . Si "simuler complètement" se réfère à la possibilité de produire le registre entier de l'ordinateur à une étape donnée i alors pour l'algorithme de Joe, il semble que PNP soit ce qui est nécessaire. Pour cette version (je pense, mais je ne suis pas sûr), la réponse de Ryan esquisse un PNP- argument de dureté. Joe a fait remarquer que si vous êtes tenus de fournir l'intégralité des registres (ce qui n'est plus un problème de décision), il n'est pas surprenant que vous deviez passer à l'étape suivante et les classes de complexité ne sont pas les mêmes.

Quoi qu'il en soit, si nous avons besoin pour sortir de l'état des registres à une étape prescrite i alors les réponses de Ruan et Joe suggère (mais encore une fois, je ne suis pas sûr à ce sujet) que NP+ est essentiellement PNP . Nous pouvons spaculate que par cette interprétation de l'opération pousse une étape ultérieure dans le hiearachy polynôme, et en ce que PH+=PH .

En tout cas, par ces interprétations, la réponse à ma question teaser est NON .

J'avais une interprétation plus drastique pour "simuler complètement un algorithme A" à l'esprit. (Mais l'interprétation de Joe et Ryan est peut-être plus intéressante.) Mon interprétation par "l'algorithme A complètement simulé" est que vous supprimez l'état des registres à chaque étape . En particulier, si l'algorithme n'est pas polynomial, votre sortie n'est pas non plus polynomiale. Sous cette interprétation drastique, je me demandais si nous devions croire que pour chaque algorithme A, C A est dur pour P-SPACE, et que pouvons-nous prouver.iCA

Motivation:

Cette question était motivée par une conférence de Paul Goldberg ( diapositives , vidéo , papier ) décrivant un papier avec Papadimitriou et Savani. Ils ont montré que l'espace P était complet pour trouver les équilibres calculés par l'algorithme de Lemke-Howson. Le problème pour trouver un point d'équilibre n'est que PPAD-complet. Cet écart est assez étonnant et des résultats similaires sont déjà décrits dans l'article bien connu de Papadimitriu: La complexité de l'argument de la parité et d'autres preuves d'existence inefficaces (1991) . (Il est connu que les problèmes complets de PPAD ne peuvent même pas être difficiles à NP (à moins que des choses terribles ne se produisent, c'est donc loin dans le monde de la complexité par rapport à l'espace P).

Quelle est la question

Ma question porte sur des lacunes similaires pour des problèmes de complexité informatique encore plus anciens et plus classiques. (Peut-être que cela est déjà familier.)

Étant donné un problème de calcul, nous pouvons distinguer trois problèmes

a) Résoudre le problème de manière algorithmique

b) Atteindre la même solution qu'un algorithme spécifique A

c) Simuler l'ensemble de l'algorithme A

Bien sûr, c) est au moins aussi dur que b) qui est au moins aussi dur que a). Les résultats mentionnés ci-dessus montrent un écart entre la difficulté de calcul des tâches a) et b) pour le problème du calcul des équilibres. Nous aimerions comprendre la situation (et principalement l'écart entre a) et c)) pour d'autres problèmes de calcul.

La question:

La forme de base de la question avec un exemple

Nous commençons par un problème de calcul, le problème X

Un exemple peut être

Problème X: résoudre une instance de SAT avec n variables

nous précisons également

A: un algorithme qui exécute le problème X

et nous posons un nouveau problème

Problème Y: simuler exactement l'algorithme A

et nous nous intéressons à la difficulté de calcul du problème Y. Nous souhaitons comprendre la classe de ces problèmes Y pour tous les algorithmes A qui résolvent le problème X d'origine. be) si nous sommes autorisés à choisir l'algorithme A à volonté.

L'opération proposée sur les classes de complexité

Commencez avec une classe de complexité qui est décrite par une tâche de calcul. Étant donné un algorithme A pour effectuer chaque instance de cette tâche de calcul, considérons une nouvelle classe de complexité C ACCA qui est décrit par la tâche de calcul de simulation completly . Ensuite, nous pouvons (espérons-le) définir un «idéal» de classes de complexitéA

pour tous les algorithmes A}.C+={CA:

Si nous laissons décrire tout ce qu'un ordinateur numérique peut faire en temps polynomial (donc je ne veux pas restreindre l'attention par exemple aux problèmes de décision), alors PP est l'idéal couvert par P lui-même.P+P

Enfin, mes questions

Mes questions sont:

1) La définition a-t-elle du sens (au sens large du mot sens). Est-ce bien connu ou identique (ou similaire à) quelque chose de bien connu. (Ma formulation était informelle et en particulier lorsque nous passons de problèmes spécifiques comme SAT à une classe de complexité comme NP, nous devons nous soucier de diverses choses que j'ai négligées.)

Les deux questions suivantes supposent que la définition peut avoir du sens ou être récupérée pour avoir du sens.

2) Supposons que nous nous équipions de toutes les conjectures standard concernant la complétude informatique. Pouvons-nous dire ce que est censé être pour certaines classes de complexité familières. (Par exemple C = N P , C = espace P, ..)? EDIT: Plusieurs personnes ont souligné que P S P A C E + = P S P A C E . Alors> on peut demander à la place ce qui est ( P N P ) + ? est P H + = P H ?C+C=NPCPSPACE+=PSPACE(PNP)+PH+=PH

Peut-on deviner quelles sont les classes de compexité pour que C + soit l'idéal recouvert par C ?CC+C

La question de la facilité avec laquelle la tâche de calcul de simuler un algorithme A pour 3-SAT (lorsque nous pouvons choisir l'algorithme pour le rendre aussi simple que possible) est donc un cas spécial intéressant.

3) Peut-on réellement prouver quelque chose sur cette opération?

Bien sûr, si vous prouvez que toutes les classes de complexité dans sont difficiles dans l'espace P, cela montrera que P = N P implique P = P S P A C E , ce qui (je pense) serait un résultat énorme et très inattendu . Mais si vous montrez que toutes les classes de complexité dans N P + sont difficiles à dire dans le troisième niveau de la hiérarchie polynomiale (par exemple Δ P 3 ), cela impliquerait seulement des choses que nous savons déjà, des choses qui découlent du fait que P = N P provoque l'effondrement du PH.NP+P=NPP=PSPACENP+Δ3PP=NP

Gil Kalai
la source
3
Question interessante! Mais: "Bien sûr, a) est au moins aussi dur que b) qui est au moins aussi dur que c)." La commande ne devrait-elle pas être l'inverse?
Bart Jansen
2
Est-il possible d'inclure un lien ou peut-être une brève description de ce que signifie «simuler l'ensemble de l'algorithme A». Par exemple, quelle est la différence entre «simuler» et «exécuter» dans ce cas? Est-il possible de simuler un algorithme plus rapidement que son temps d'exécution?
Artem Kaznatcheev
1
Cher Artem, en simulant un algorithme sur une instance spécifique, je veux dire décrire toute l'évolution de l'algorithme. (Alors peut-être que c'est comme "exécuter" l'algorithme.) Vous ne pouvez pas simuler l'algorithme plus rapidement que son temps d'exécution. Ce n'est pas une notion standard (à ma connaissance), donc je ne peux pas donner de liens ou de références (mais j'espère obtenir des liens et des références.). La simulation de l'algorithme est différente de la simple tâche de calcul de "donner la même sortie que l'algorithme A" qui est liée à la motivation et à la tâche b) décrites dans la question.
Gil Kalai
2
Cher Gil, je ne vois pas pourquoi nous ne pouvons pas simuler un algorithme avec des ressources du même ordre que A utilise. À moins que certaines ressources sont plus limitées que nous pouvons simplement simulons tout A fait. Permettez - moi de voir si je comprends la partie de la motivation correctement: Nous avons un problème Q dans la classe C . A est un algorithme éventuellement en dehors de C résolution Q . Bien que la recherche d' une solution pour Q peut être fait en C , trouver une des les solutions A découvertes peuvent avoir la complexité en dehors CAAAQCACQQCAC. Suis-je en train de comprendre correctement la partie motivation du poste?
Kaveh
2
Oui oui nous supposons que l'algorithme A est déterministe! Je n'ai pas une intuition claire pour laquelle nous devrions nous attendre à ce que la simulation de chaque algorithme déterministe pour 3-SAT soit un espace P difficile. Ceci est la question! Je voulais voir ce que pensent les experts.
Gil Kalai

Réponses:

12

Problème: Soit A un algorithme déterministe pour 3-SAT. Le problème de la simulation complète de l'algorithme A (sur chaque instance du problème) P-Space est-il difficile?

Je ne comprends pas l'énoncé de ce problème. Mais je pense qu'il y a un moyen naturel de formaliser votre question plus générale qui pourrait l'éclairer un peu. Peut-être que je manque complètement votre point de vue, mais j'espère que vous trouverez toujours quelque chose d'intéressant à lire ici.

1) La définition a-t-elle du sens (au sens large du mot sens). Est-ce bien connu ou identique (ou similaire à) quelque chose de bien connu. (Ma formulation était informelle et en particulier lorsque nous passons de problèmes spécifiques comme SAT à une classe de complexité comme NP, nous devons nous soucier de diverses choses que j'ai négligées.)

Une façon de donner un sens à la tâche simuler exactement l'algorithme Y est la suivante. Corrigeons le modèle en machines de Turing à une bande pour plus de simplicité; ce que je vais dire peut s'appliquer à tout modèle de calcul typique.

Pour chaque algorithme et entrée x , on peut définir son historique de calcul H Y ( x , i , j ) : Entiers donnésYx HY(x,i,j) et j qui vont de 0 au temps de fonctionnement de Y , H Y ( x , i , j ) est égal à le contenu de la j ème cellule de la bande de la machine Turing Y sur l'entrée x au pas de temps i . (Et si la tête de lecture lit le jij0YHY(x,i,j)jYxije cellule dans la ème étape, incluez cela aussi avec l'état de la machine.) Bien sûr, les historiques de calcul reviennent tout le temps dans la théorie de la complexité.i

Maintenant, on pourrait faire valoir que tout algorithme qui peut décider de la langue

CY={(x,i,j,σ) | HY(x,i,j)=σ}

(ou simuler la fonction sur toutes les entrées) est la résolution de la tâche exactement algorithme Simuler Y , car il a la possibilité d'imprimer chaque petite partie de chaque calcul possible de l' algorithme Y . Certes, étant donné un oracle pour C Y on pourrait faire une simulation étape par étape de Y .HYYYCYY

2) Supposons que nous nous équipions de toutes les conjectures standard concernant la complexité de calcul. Pouvons-nous dire ce que C + est censé être pour certaines classes de complexité familières. (Par exemple C = NP, C = espace P, ..)? Peut-on deviner quelles sont les classes de complexité C pour que C + soit l'idéal recouvert par C?

C'est toujours une question intéressante, dans le cadre de la proposition ci-dessus. Pour les classes horaires déterministes, rien ne change. est juste P : on peut décider que C Y H Y n'est plus bien défini. Cependant, nous voulons toujours imprimer un historique de calcul, de sorte que notre "simulation exacte" devrait isoler un historique de calcul non déterministe spécifique, puis imprimer ses valeurs. Pour un NP+PCY en polytime, pour chaque algorithme de polytime. De même . Aussi P S P A C E + est toujours P S P A C E . Pour les classes de complexité temporelle non déterministes, la situation devient plus intéressante. Dans ce cas, un algorithme Y peut avoir plusieurs historiques de calcul, doncEXP+=EXPPSPACE+PSPACEYHYalgorithme P Y , on peut dire que C YP N P : on peut utiliser l'oracle N P pour rechercher binaire le "premier" historique de calcul acceptant (dans l'ordre lex), puis une fois que nous l'avons obtenu, imprimer les bits pertinents. Pour unalgorithme N E X P Y , on peut dire C YNPYCYPNPNPNEXPY , pour des raisons similaires.CYEXPNP

Peut-on mettre dans une classe plus petite? Je ne sais pas. Notez que nous ne pouvons pas simplement redéfinirNP+

{ ( x , i , j , σ ) | il existe un H Y tel que H Y ( x , i , j ) = σ }CY=(x,i,j,σ) | HYHY(x,i,j)=σ

pour essayer de mettre dans N P , car nous avons besoin que la chaîne d'historique soit la même pour tous les quadruples impliquant x , afin de "simuler exactement l'algorithme Y ".CYNPxY

Quoi qu'il en soit, ce problème de ne pas pouvoir "imprimer un témoin" sur un calcul sans passer par E X P N P se pose dans certaines situations, telles que la complexité du circuit. Si N E X P a des circuits de taille polynomiale, alors est-ce aussi le cas que C YP / p o l y pour chaque 2 n k temps Y non déterministe ?NEXPEXPNPNEXPCYP/poly2nkYImpagliazzo, Kabanets et Wigdersona répondu à cette question par l'affirmative en 2001. Leur preuve est extrêmement intéressante, invoquant des outils de dérandomisation et de diagonalisation (pourquoi la dérandomisation serait-elle nécessaire pour un tel résultat?) et il s'avère être un théorème très utile pour prouver les limites inférieures du circuit pour Fonctions P.NEXP

Peut-on réellement prouver quelque chose sur cette opération?

Peut-être ... cela dépend si vous êtes satisfait de la formalisation de votre question ci-dessus. Pour un algorithme déterministe 3-SAT , je pense que la simulation exacte ci-dessus du problème Y serait P N P ( 1 )YYPNP(1) -hard, où est polynomiale avec une requête N P . (La syntaxe ennuyeuse de StackExchange nécessite que j'écrive (1) au lieu de l'alternative. Plus tôt, j'ai dit que C Y devrait être P N P -hard, mais je ne suis pas sûr des détails: vous pouvez voir comment généraliser ce qui suit.)PNP(1)NPCYPNP

Nous donnons un polynomial beaucoup-une réduction de chaque à C Y . Étant donné un tel L , soit MLPNP(1)CYLM une machine reconnaissant qui effectue une seule requête N P. WLOG, cette requête est une formule SAT. Également WLOG, la requête SAT peut être "reportée" jusqu'à la toute dernière étape du calcul, dans le sens suivant: il existe un algorithme de temps polynomial A ( x ) qui imprime une formule F et le bit b , tels que pour tout x ,LNPA(x)Fbx

accepte ssi A ( x ) = ( F , b ) tel que ( S A T ( F ) XOR b ) = 1.M(x)A(x)=(F,b)SAT(F)b

( peut rejeter ssi F est satisfaisable, ou il peut accepter; le bit b capture cela.)MFb

Par souci de simplicité, disons que lorsque termine son calcul, il déplace sa tête de bande vers la cellule 1, écrit «accepter» ou «rejeter» dans cette cellule et boucle pour toujours. Ensuite, demander si ( F , T , 1 , a c c e p t ) C Y pour T suffisamment grand nous dira si F est accepté. (En général, nous avons juste besoin qu'il soit efficace de calculer l'instance y de C Y qui nous le dira.) Notez que cela montre déjà que C Y est à la fois N P -hard etY(F,T,1,accept)CYTFyCYCYNP -hard; cette dernière est vraie parce que ( F , T , 1 , r e j e c t ) C Y ssi F n'estpassatisfaisable.coNP(F,T,1,reject)CYF

La réduction finale de à C Y est: étant donné x , exécutez A ( x ) obtenant ( F , b ) . Si b = 0 alors sortie ( F , T , 1 , a c c e p t ) , sinon si b = 1 sortie ( F , T , 1 , r e j e c tLCYxA(x)(F,b)b=0(F,T,1,accept)b=1 .(F,T,1,reject)

Pour chaque nous produisons (en temps polynomial) un y tel que M ( x ) accepte ssi y C Y .xyM(x)yCY

(Merci à Joe d'avoir exigé que je sois plus clair sur cette partie.)

Mais je ne vois pas (par exemple) comment obtenir la dureté Pour réduire Σ 2 -SAT au problème, il semblerait que vous deviez écrire une instance SAT 3-CNF x qui simule votre algorithme déterministe Y en son sein (où Y résout les tautologies sur divers sous-problèmes). Mais comme Y n'a pas de limite de temps donnée, ce 3-CNF x pourrait être énorme, donc vous n'obtenez pas nécessairement une réduction du temps polynomial. A moins que je manque quelque chose.Σ2PΣ2xYYYx

Ryan Williams
la source
Ryan, merci beaucoup pour votre réponse. Je suis intéressant de voir combien il est difficile de simuler un algorithme déterministe Y pour 3-SAT. Et la question est de savoir si, quel que soit Y, il s'agit d'un espace P dur. (Votre compréhension de la simulation d'algorithmes non déterministes est également intéressante et peut-être la bonne question, mais j'ai seulement envisagé de simuler des algorithmes déterministes.)
Gil Kalai
Oui, je pensais que le dernier paragraphe de ma réponse aborderait cette partie.
Ryan Williams
Je vois. Oui, en effet. J'ai également soupçonné que cela pourrait être prouvablement -hard qui est intéressant (mais je ne suis pas sûr de comprendre votre preuve). Vous attendez-vous à ce que P N P soit la bonne réponse? Je soupçonnais également qu'il serait difficile de prouver quelque chose au-delà de P N P. Revenant de ce que nous pouvons prouver à ce que nous devons croire, Ryan, quelle est selon vous la réponse? PNPPNPPNP
Gil Kalai
Eh bien, la complexité de varie en fonction de l'algorithme Y . Certains C Y peuvent être très difficiles et d'autres beaucoup plus faciles. Mais je pense que pour chaque algorithme Y , vous ne ferez probablement pas beaucoup mieux que de dire " C Y est P N P -hard". (Je ne pense pas que pour chaque Y, vous pouvez obtenir une dureté Σ 2 P , pour la raison intuitive que j'ai donnée ci-dessus.)CYYCYYCYPNPYΣ2P
Ryan Williams
Ryan, vous dites que « il y a une réduction polynomiale d'un langage complet ... à C Y », mais votre réduction semble utiliser plusieurs instances de C Y . Cela montre sûrement à la place qu'il existe une réduction polynomiale d'un problème P N P -complet à P C Y ? PNPCYCYPNPPCY
Joe Fitzsimons
7

J'ai initialement publié une réponse incorrecte, donc j'espère que c'est une amélioration.

Je vais commencer par considérer l'exemple 3SAT. Dans votre commentaire sur la réponse de Ryan, vous dites

Je suis intéressant de voir combien il est difficile de simuler un algorithme déterministe Y pour 3-SAT. Et la question est de savoir si, quel que soit Y, il s'agit d'un espace P dur.

La réponse à cela est qu'il n'est pas dur pour PSPACE pour au moins certains Y, en supposant que NP PSPACE, mais qu'il existe d'autres algorithmes pour lesquels il est dur pour PSPACE. Montrer ce dernier est trivial: nous construisons simplement un algorithme qui interprète la chaîne de bits représentant la formule 3SAT à la place comme un problème TQBF, qu'il résout ensuite avant de résoudre l'instance 3SAT. Évidemment, il n'y a rien de spécial à propos de TQBF dans ce cas, donc l'algorithme peut être rendu arbitrairement difficile à simuler. Nous ne devons donc nous soucier que des limites inférieures lors de la simulation d'un algorithme pour un problème donné, plutôt que d'un algorithme spécifique.

Dans cet esprit, nous construisons l'algorithme suivant pour résoudre 3SAT:

Prendre un registre de bits (initialement tous mis à 0) pour contenir une solution d'essai, ainsi qu'un registre contenant l'instance 3SAT, un registre de compteur de taille log 2 ( c + 1 ) initialement défini sur 1 et et deux flag bits (appelez-les drapeau d’échec et drapeau d’acceptation). Ici c est le nombre de clauses. L'algorithme procède ensuite comme suit:nlog2(c+1)c

  • Si la valeur du compteur de clauses est inférieure ou égale à ckc et que la solution d'essai n'est pas , vérifiez si la clause k est satisfaite. Sinon, définissez le bit d'échec. Incrémentez le compteur.111......1k
  • Si la valeur du compteur de clauses est inférieure ou égale à ckc et que la solution d'essai est , vérifiez si la clause k est satisfaite. Si ce n'est pas le cas, définissez l'indicateur d'échec. Incrémentez le compteur.111......1k
  • Si dépasse c et que la solution d'essai n'est pas 111 ...... 1 , vérifiez si l'indicateur d'échec est défini. Si tel est le cas, incrémentez la solution d'essai, réinitialisez le compteur k à 1 et désactivez l'indicateur d'échec. Si l'indicateur d'échec n'a pas été défini, définissez l'indicateur d'acceptation, définissez le compteur de clauses k sur zéro, définissez la solution d'essai sur zéro et arrêtez.kc111......1kk
  • Si dépasse c et que la solution d'essai est 111 ...... 1 , vérifiez si l'indicateur d'échec est défini. Si l'indicateur d'échec n'a pas été défini, définissez l'indicateur d'acceptation. Mettez le compteur de clauses k à zéro, mettez la solution d'essai à zéro et arrêtez.kc111......1k

Lorsque l'algorithme s'arrête, l'état de l'indicateur d'acceptation vous indique si la formule 3SAT peut être satisfaite ou non.

Maintenant, si je veux calculer l'état de l'algorithme au moment j'ai un algorithme pour le calculer en temps polynomial avec un seul appel à un oracle NP comme suit:i

Notez que pour tout , en supposant que le bit d'acceptation n'est pas encore défini, l'état des registres peut être calculé en temps polynomial, car la valeur de k et le registre de solution d'essai t sont simplement des fonctions de i . Il est possible de déterminer si l'indicateur d'échec est défini en temps polynomial, simplement en vérifiant si l'état actuel du registre de solution d'essai satisfait toutes les clauses inférieures ou égales à la valeur actuelle de k . Si et seulement si ce n'est pas le cas, l'indicateur d'échec est défini. L'indicateur d'acceptation est mis à zéro.iktik

De même, si le bit d'acceptation a déjà été défini, l'état des registres peut être calculé efficacement, car tout est nul sauf le bit d'acceptation, qui est défini.

Ainsi, la seule dureté vient de déterminer si le bit d'acceptation est défini. Cela revient à déterminer si l'instance 3SAT donnée a une solution inférieure à . Si c'est le cas, alors le bit d'acceptation doit nécessairement être défini, et s'il ne le fait pas, alors le bit d'acceptation doit nécessairement être nul. Clairement, ce problème est lui-même NP-complet.t

Ainsi, l'état du système à l'étape peut être déterminé en temps polynomial avec une seule requête à un oracle NP.i

Mise à jour importante: au départ, j'avais mal interprété la formulation de Ryan de la simulation exacte en tant que problème de décomposition, et donc mon affirmation selon laquelle la version de décission était en NP était incorrecte. Étant donné le problème de décider si le bit à l'étape i sur l'entrée x tel que formulé dans la réponse de Ryans, alors il y a 3 possibilités:jix

  1. Ce bit est constant indépendamment du fait que soit satisfaisable. Comme il n'y a que deux états possibles pour le système à ce moment (qui peuvent tous deux être calculés dans P), déterminer si c'est le cas, et si oui, si la valeur est égale à σ est dans P.Fσ
  2. Le bit est égal à si F S A T , et inégal sinon. Ce problème est clairement dans NP, car l'affectation satisfaisante de F agit comme témoin.σFSATF
  3. Le bit est égal à si F U N S A T auquel cas le problème est alors en coNP.σFUNSAT

Il est clair que de décider lequel de ces trois est le cas peut être réalisé en temps polynomial, simplement en comparant la valeur que prend bit si et si F U N S A T . Ainsi, le problème de simulation exact est dans NP coNP. Ainsi, comme minorant Ryan et mon match majorant, si les deux sont corrects, je pense que nous avons une réponse: C Y = N P de la c o N P .FSATFUNSATCY=NPcoNP

i

Joe Fitzsimons
la source
1
Can't you use the same technique to show that b) Reaching the same solution as algorithm A is already PSPACE-hard? Have the algorithm choose between one of two possible solutions depending on the solution of a PSPACE-hard problem encoded into the input.
Peter Shor
1
@Peter: Sure, you could make it arbitrarily hard, but I thought the interesting question was the upper bound minimized over A, which turns our to be NP.
Joe Fitzsimons
3

Very interesting thought! Here's an extended comment that was too long to post as such:

Regarding the definition in (1) as such, that is:

Start with a complexity class C which is described by some computational task. Given an algorithm A to perform every instance of this computational task, consider a new complexity class CA which is described by the computational task of completly simulating A. Then we can (hopefully) define an "ideal" of complexity classes: C+={CA: for all algorithms A}.

I believe you're going to quickly run into an issue with undecidability for non-trivial membership in C+. In particular, given the description of two TMs M and M, it's well-known that deciding whether they accept the same language (i.e. L(M)=?L(M) is undecidable in general by reduction from the Halting Problem.

Further, given the description of a Turing Machine , there is always a trivial simulation: Just construct a new Turing Machine M that calls M as a subroutine (using its description), which accepts if M accepts and rejects if M rejects. This only costs a linear overhead. Specifically, if M runs in t(n) computational steps, then M runs in O(t(n)) (whereby "run," I mean "simulates M exactly").

This suggests to me that if there's any serious traction to be gained here, the precise way you go about making the definition of the ideal of a complexity class is going to be fairly important. In particular, if you intend to show that the ideal of, say, NP is PSPACE-hard, you'll have to rule out the notion of a trivial, linear-time simulation of the NP machines in question.

With respect to the homotopy methods described in the talk/paper and GPS's PSPACE-completeness result, I believe the "gap" you're witnessing between PPAD-completeness and PSPACE-hardness is due to the distinction between finding any NE (in the sense of END OF LINE) and finding a unique NE given a specific, initial configuration (in the sense of OTHER END OF LINE).

Daniel Apon
la source
Dear Daniel, thanks for your answer. I am not sure I see why undecidability of membership in C^+ (Or even in C itself) is relevant to the question. The questions if :a) based on all our conjectures and beliefs regarding seperations of complexity classes is it the case that for every algorithm A for 3-SAT the computational task of simulating A (for every instance of 3-SAT) is Δ3P hard. b) Is it possible to actually proves such (or a similar) statement.(Maybe something very basic is wrong with my questions but I am not sure decidability is the issue.)
Gil Kalai
Gil, see if this speaks to your question at all: Fix some (arbitrary) algorithm A for 3-SAT. Consider a new algorithm B. Then we want to claim: B simulates A, in the sense of your (b) -- i.e. that B reaches the same solutions as A on all well-defined inputs. Since we can view algorithms as Turing machines, we can take the view that A accepts 3-SAT (by the supposition). To prove the claim, it appears to me that we then need to decide the question "Does B (viewed as a TM) accept 3-SAT as well?", which leads into undecidability issues.
Daniel Apon
I should point out that it's specifically the phrase "for all algorithms A" in the definition of C+ coupled with the notion of saying/guessing (or, presumably, computing or deciding) the elements of the set that gives me pause, if nothing else. Once we start considering computation on properties of arbitrary algorithms or languages or classes/sets of languages, the Halting problem often seems to creep in.
Daniel Apon
1
Dear Daniel, you wrote "Then we want to claim: B simulates A, in the sense of your (b) -- i.e. that B reaches the same solutions as A on all well-defined inputs." This is not what I mean by "B simulates A". For me B simulates A means that it describes precisely the entire "running" of algorithm A not just reach the same "solutions" (or output).
Gil Kalai
1
Regarding your second comment. It looks that we can find a reasonable restriction on the algorithms we consider or formulate the question a little differently: E.g. consider the statement "For every algorithm A to solve 3-SAT it is P-space hard to simulate A." I dont see how the halting problem creep in (more than in other questions in computational complexity).
Gil Kalai