Un problème NP-difficile peut-il être polynomial en moyenne?

Je me demande s'il y a des problèmes durs qui sont "polynomiaux" dans le cas moyen. Je pense qu'il y a deux façons d'interpréter cela? $NP$

Si , peut-il y avoir un algorithme résolvant un problème dur avec un temps d'exécution amorti (cas moyen) de pour une constante ? $P \neq NP$ $NP$ $O(n^k)$ $k$
Y a-t-il des problèmes qui sont dur qui sont également dans , ou même ? $NP$ $BPP$ $PP$

Quelqu'un peut-il répondre ou fournir une référence répondant à l'une de ces questions?

complexity-theory reference-request np-complete probabilistic-algorithms amortized-analysis jmite
la source

Cette question est apparue dans la théorie CS il y a quelque temps, voici le lien cstheory.stackexchange.com/questions/496/…

lPlant

Ah, excellent! Dois-je alors fermer / supprimer cette question?

jmite

@jmite: Cela peut être utile de rester ici, alors peut-être publier une (auto-) réponse rapide avec une référence ici?

Raphael

Je voudrais simplement souligner que l'amortissement n'est pas le même que le temps de fonctionnement moyen.

gardenhead

Si un problème NP-difficile est dans BPP, cela signifie que NP est dans BPP, ce qui signifie que la hiérarchie polynomiale s'effondre, un résultat qui est considéré comme peu probable. En revanche, je ne pense pas qu'il ne soit pas considéré comme très improbable que PP contienne NP depuis . (Vous voudrez peut-être poser des questions sur les preuves pour et contre NP dans PP sur l' informatique théorique .)

P H \subseteq P^{P P}

$PH \subseteq P^{PP}$

Kaveh

Un problème NP-difficile peut-il être polynomial en moyenne?

Réponses: