Pourquoi n'utilisons-nous pas des classes plus grandes pour étudier le déterminisme contre le non-déterminisme?

Dans une question précédente sur la hiérarchie temporelle, j'ai appris que les égalités entre deux classes peuvent être propagées à des classes plus complexes et les inégalités peuvent être propagées à des classes moins complexes, avec des arguments utilisant le remplissage.

Par conséquent, une question me vient à l'esprit. Pourquoi étudions-nous une question sur différents types de calcul (ou ressources) dans la plus petite classe (fermée) possible?

La plupart des chercheurs pensent que . Cette distinction de classes ne serait pas entre les classes qui utilisent le même type de ressource. Par conséquent, on pourrait considérer cette inégalité comme une règle universelle: le non-déterminisme est une ressource plus puissante. Par conséquent, bien qu'il s'agisse d'une inégalité, elle pourrait se propager vers le haut en exploitant la nature différente des deux ressources. On peut donc s'attendre à ce que aussi. Si l'on prouvait cette relation ou toute autre inégalité similaire, cela se traduirait par . $P \neq NP$ $EXP \neq NEXP$ $P \neq NP$

Mon argument pourrait peut-être devenir clair en termes de physique. Newton aurait du mal à comprendre la gravité universelle en examinant les roches (pommes?) Au lieu des corps célestes. L'objet plus grand offre plus de détails dans son étude, donnant un modèle plus précis de son comportement et permettant d'ignorer les phénomènes à petite échelle qui pourraient ne pas être pertinents.

Bien sûr, il y a le risque que dans les objets plus grands il y ait un comportement différent, dans notre cas, la puissance supplémentaire du non-déterminisme ne serait pas suffisante dans les classes plus grandes. Et si après tout, était prouvé? Faut-il commencer à travailler sur le lendemain? $P \neq NP$ $EXP \neq NEXP$

Considérez-vous cette approche problématique? Connaissez-vous des recherches qui utilisent des classes plus grandes que les polynômes pour distinguer les deux types de calcul?

cc.complexity-theory big-picture chazisop
la source

Je pense que les mêmes barrières qui rendent difficile la démonstration de P! = NP rendent difficile la séparation de EXP et NEXP. Par exemple, je crois qu'il y a un résultat de non-relativisation pour EXP et NEXP. Je suis sûr que les gens ont considéré les questions de séparation concernant les classes de complexité plus grandes, mais j'imagine que cela n'a pas conduit à plus de progrès que d'essayer de séparer les plus petites.

Philip White

Je viens de relire vos derniers paragraphes; J'ai peut-être mal lu votre question. Demandez-vous: "pourquoi ne pouvons-nous pas séparer P! = NP en examinant des conjectures connexes comme EXP! = NEXP?" ou demandez-vous, "pourquoi P? = NP at-il été choisi au lieu d'une question différente pour explorer les différences entre le déterminisme et le non-déterminisme?" Je suppose que vous savez que P = NP -> EXPTIME = NEXPTIME. La réponse à la deuxième question, je pense, est liée au fait que P est faisable, alors que EXPTIME ne l'est pas. De plus, NP est pertinent pour la cryptographie. Je pense que P? = NP semble juste plus "pertinent".

Philip White

La deuxième question est ma principale question. Cependant, la première question est également liée: pouvons-nous séparer le non-déterminisme du déterminisme une fois pour toutes ou sommes-nous condamnés à essayer de résoudre des questions P! = NP infinies, à chaque fois avec des classes plus importantes? Je soutiens également que bien que P et NP soient pertinents pour nos problèmes "humains", peut-être que des classes plus grandes qui sont irréalisables sont nécessaires pour comprendre le pouvoir du non

chazisop

Réponses:

Le problème peut être un peu plus propre avec et . La façon la plus simple de penser à ces classes est qu'elles sont identiques à et mais limitées aux langages unaires . Autrement dit, toutes les entrées sont de la forme . $E=Dtime(2^{O(n)})$ $NE=Ntime(2^{O(n)})$ $P$ $NP$ $1^k$

C'est-à-dire que le langage est en si et seulement si le langage est en (identifiant les chaînes avec des nombres en utilisant une représentation binaire), et de même est isomorphe à unaire . $L$ $E$ $U_L = \{ 1^x : x\in L \}$ $P$ $NE$ $NP$

Donc, essayer de séparer de c'est comme essayer non seulement de séparer de , mais de le faire en utilisant un langage unaire. Aucune raison pour que cela vous rende la vie encore plus facile conceptuellement. $NE$ $E$ $P$ $NP$

Boaz Barak
la source

Cela semble clarifier la situation. On pourrait donc dire que implique qu'il n'y a pas d'algorithme général qui permet une simulation polynomiale d'un NTM par un DTM, alors que des déclarations similaires pour des classes plus importantes impliquent la même déclaration mais pour des langages plus spécifiques?

P \neq N P

$P \neq NP$

chazisop

Oui en effet (pour les familles de langues plus restreintes)

Boaz Barak

Pourquoi nous choisissons de nous soucier de vs ? En fait, le non-déterminisme comme objet d'étude n'est qu'une préoccupation secondaire. Nous nous soucions vraiment du raison des milliers de problèmes importants qui sont liés au . Ce sont des problèmes que nous voulons (et dans la vraie vie devons ) résoudre. Nous nous soucions de savoir si ces problèmes peuvent être résolus efficacement, et est notre modèle théorique pour un calcul efficace. Nous sommes donc amenés à la question de vs . $P$ $NP$ $NP$ $NP$ $P$ $P$ $NP$

Kristoffer Arnsfelt Hansen
la source

Notez qu'il existe des séparations connues pour certaines classes de complexité illimitées, par exemple , et également des égalités comme et . (Il est instructif de réfléchir à la raison pour laquelle le remplissage trivial qui les utilise n'est pas utile pour régler P vs NP.) Nous devrions être plus prudents sur ce que nous entendons par une question comme vs et vs . Si vs est une version rembourrée de celui-ci (par exemple vs et vs $decidable \neq computability \ enumerable$ $NPSpace = PSpace$ $primitive \ recursive = nondeterministic \ primitive \ recursive$ $P$ $NP$ $EXP$ $NEXP$ $P$ $NP$ $EXP$ $NEXP$ $E$ $NE$ ), la réponse de Boaz lui sera également applicable.

Les preuves pour sont beaucoup plus faibles que et ont des conséquences moins dramatiques, et il y a des gens qui trouvent plausible donc la situation est plus compliquée là-bas et nous avons une intuition beaucoup plus faible sur la réponse attendue. Une égalité n'aidera pas en pratique et on ne sait pas qu'elle a un effet sur le cas vraiment intéressant qui est vs , et une inégalité est formellement et conceptuellement aussi difficile qu'une inégalité entre vs . $EXP \neq NEXP$ $P \neq NP$ $EXP = NEXP$ $P$ $NP$ $P$ $NP$

Kaveh
la source

E X P \neq N E X P

$EXP \ne NEXP$ implique , donc je ne comprends pas votre affirmation selon laquelle les preuves pour sont beaucoup plus faibles. Notez que implique tht ce qui est un résultat très surprenant.

P \neq N P

$P \ne NP$

E X P \neq N E X P

$EXP \ne NEXP$

E X P = N E X P

$EXP = NEXP$

N E X P = c o - N E X P

$NEXP = co-NEXP$

Mohammad Al-Turkistany

@turkistany: Merci pour le commentaire (bien que je ne trouve pas que ce soit une bonne raison pour voter contre). Je pensais que c'était clair, implique mais pas l'inverse, donc une preuve pour ne semble pas être une preuve pour . En tout cas serait beaucoup moins surprenant que , n'est-ce pas?

E X P \neq N E X P

$EXP \neq NEXP$

P \neq N P

$P \neq NP$

P \neq N P

$P \neq NP$

E X P \neq N E X P

$EXP \neq NEXP$

E X P = N E X P

$EXP=NEXP$

P = N P

$P=NP$

Kaveh

@Kaveh, permettez-moi d'être en désaccord. Je trouve que est un résultat très surprenant car il implique comme je l'ai dit ci-dessus.

E X P = N E X P

$EXP = NEXP$

N E X P = c o - N E X P

$NEXP =co-NEXP$

Mohammad Al-Turkistany

@turkistany: Il est clair pour moi que serait bien plus surprenant que , mais bien sûr, vous pouvez être en désaccord avec cela. :)

P = N P

$P = NP$

E X P = N E X P

$EXP=NEXP$

Kaveh

Comment définissez-vous récursif primitif non déterministe?

slimton