ALogTime! = PH est-il difficile à prouver (et inconnu)?

Lance Fortnow a récemment affirmé que prouver L! = NP devrait être plus facile que prouver P! = NP :

NP séparé de l'espace logarithmique. J'ai donné quatre approches dans une enquête pré-blog 2001 sur la diagonalisation (section 3), mais aucune n'a échoué. Cela devrait être beaucoup plus facile que de séparer P de NP.

La section 3 de l'enquête couplée affirme qu'il n'y a aucun résultat significatif d'effondrement d'Oracle:

Alors que la question P! = NP reste assez formidable, la question L! = NP semble beaucoup plus traitable. Nous n'avons aucune raison de penser que cette question est difficile. L'absence de bons modèles de relativisation de l'espace signifie que nous n'avons pas de modèle d'oracle significatif où L et NP s'effondrent. De plus, puisque L est une classe uniforme, les limitations de Razborov-Rudich [RR97] ne s'appliquent pas.

UNE question sur les barrières de relativisation connues de L! = NP sur ce site a obtenu une réponse soulignant que le problème complet de PSPACE TQBF peut être utilisé comme oracle pour obtenir un tel effondrement. Une objection à savoir s'il s'agissait d'un modèle d'oracle significatif semble également trouver une réponse.

Mais même si je comprenais pourquoi "nous n'avons pas de modèle d'oracle significatif où L et NP s'effondrent" devrait être considéré comme une déclaration correcte, j'aurais quand même des doutes si prouver L! = NP est plus faisable que prouver P! = NP. Si prouver L! = NP devrait vraiment être plus facile que prouver P! = NP, alors prouver ALogTime! = PH devrait être définitivement à portée de main. (L'article de l'enquête suggère la possibilité de séparer de ) Je suppose que ALogTime! = PH est toujours ouvert, et je voudrais savoir s'il y a de bonnes raisons de s'attendre à ce qu'il soit difficile à prouver. $\Sigma_2^p$ $L$

cc.complexity-theory reductions relativization Thomas Klimpel
la source

Lance Fortnow 7 h 03, le 13 mai 2016 : "Permettez-moi de reformuler mon propos. Soit AP une alternance de polytemps (connue pour être PSPACE non relativisée et donc différente de L). Ensuite, il n'y a pas de modèle de relativisation connu qui fasse tous les deux L = NP pour certains oracles, mais sépare L de AP pour tous les oracles. "

Thomas Klimpel

Réponses:

$L$ $NP$ $L = NL$ $L^A = NL^A$ $A$

$NC1$ $ALogTime = NP$ $NC1$ $NP$ $NC1$ http://link.springer.com/article/10.1007/BF01692056 . (Une mise en garde: techniquement parlant, cet article considère l'uniforme LOGSPACE NC1, mais je pense qu'une version raisonnable de cette construction oracle devrait fonctionner dans le cadre uniforme LOGTIME.)

Au-delà de cela, je ne connais aucune raison particulière de croire qu'il est "difficile à prouver" autre que l'observation que de nombreuses personnes ont essayé et qu'aucune n'a encore réussi.

Ryan Williams
la source

L = N L

$L = NL$

L^{A} = N L^{A}

$L^A = NL^A$

A

$A$

L

$L$

Je crois qu'il y a une preuve de la déclaration dans le document que j'ai lié. Concernant votre deuxième phrase: demandez-vous pourquoi Fortnow dit que Razborov-Rudich ne s'applique pas? Si tel est le cas, son point de vue est que la barrière des preuves naturelles, telle qu'elle est communément comprise, ne s'applique que si le modèle contre lequel vous vous limitez est non uniforme, par exemple P / poly.

Ryan Williams

Ah, j'ai mal lu: je pensais que la barrière qui ne s'appliquait pas était la relativisation, pas les preuves naturelles, désolé. Ce que je voulais demander était: pourquoi la relativisation est-elle une barrière pour P vs NP mais pas L vs NL, moralement? (D'où la non-relation de la question.)

Michaël Cadilhac

En bref, c'est parce que le modèle Oracle RST ne vous permet pas de faire des étapes non déterministes à moins que la bande Oracle ne soit vierge. (Les raisons en sont subtiles; fondamentalement, certains résultats ne se relativiseront pas sans cela.) L'argument réel est plus compliqué ...

Ryan Williams

Une idée naïve pour prouver ALogTime! = PH: Le problème de la valeur de la formule booléenne est complet pour ALogTime sous des réductions de temps de journal déterministes . Par conséquent, si ALogTime = PH, alors PH = coNP = ALogTime, et donc le problème de la valeur de la formule booléenne serait complet sous des réductions de temps logarithmiques déterministes pour coNP. Il y aurait donc une réduction déterministe du temps de log du problème de tautologie au problème de valeur de formule booléenne.

Les réductions déterministes du temps de log devraient être inoffensives, elles ne peuvent pas beaucoup contribuer à la solution du problème de tautologie. Ils sont juste une belle formalisation ce que cela signifie qu'une réduction ne peut fonctionner que très localement. Par conséquent, la tâche restante consiste à comprendre pourquoi le problème de tautologie ne peut pas être transformé en un problème de valeur de formule booléenne par des réductions très locales. Je ne vois toujours pas comment faire cela, mais au moins la tâche restante est très claire, de sorte que j'ai au moins une chance de comprendre pourquoi c'est difficile (ou pas).

Thomas Klimpel
la source