Questions marquées «cc.complexity-theory»

12
comme oracle

Est-ce que NPNP∩coNP=NPNPNP∩coNP=NP\mathsf{NP^{NP \,\cap\, coNP}=NP}maintenez? Clairement NPNP≠NPNPNP≠NP\mathsf{NP^{NP}\neq NP} , mais il me semble que NP∩coNPNP∩coNP\mathsf{NP\cap coNP} est "déterministe" ce qui me fait croire que c'est vrai. Existe-t-il une preuve simple (ou peut-être juste par...

12
La dureté APX n'implique aucun QPTAS?

Donc, une recherche rapide sur le Web m'a amené à croire que "APXHardness implique qu'aucun QPTAS n'existe pour un problème à moins que [une certaine classe de complexité] ne soit incluse dans une [autre classe de complexité]" et c'est bien connu aussi! Il semble que tout le monde le sait, sauf...

12
P / poly

P/ poly= NP/ polyP/poly=NP/polyP/poly = NP/poly impliqueNP⊆ P/ polyNP⊆P/polyNP \subseteq P/poly , qui à son tour a des conséquences intéressantes comme l'effondrement de la hiérarchie polynomiale. Y a-t-il des implications intéressantes pour P/ poly≠ NP/ polyP/poly≠NP/polyP/poly \neq NP/poly...

12
Complétude sous les réductions de Karp injectives

La réduction de Karp est une réduction de plusieurs un calculable en temps polynomial entre deux problèmes de calcul. De nombreuses réductions de Karp sont en fait des fonctions individuelles. Cela soulève la question de savoir si chaque réduction de Karp est injective (fonction one-one). Y a-t-il...