Classes de complexité pour les cas autres que le «pire cas»

Avons-nous des classes de complexité concernant, disons, la complexité moyenne des cas? Par exemple, existe-t-il une classe de complexité (nommée) pour les problèmes qui prennent le temps polynomial attendu pour se décider?

Une autre question considère la meilleure complexité de cas , illustrée ci-dessous:

Existe-t-il une classe de problèmes (naturels) dont la décision nécessite au moins un temps exponentiel?

Pour clarifier, considérons un langage complet pour EXP . De toute évidence, toutes les instances de nécessitent pas de temps exponentiel: il existe des instances qui peuvent être décidées même en temps polynomial. Donc, la meilleure complexité des cas de n'est pas le temps exponentiel.$L$$L$$L$

EDIT: Depuis que plusieurs ambiguïtés sont apparues, je veux essayer de le clarifier encore plus. Par complexité du «meilleur cas», j'entends une classe de complexité dont la complexité des problèmes est limitée par une fonction. Par exemple, définissez BestE comme la classe de langages qui ne peut pas être décidée en temps inférieur à une certaine exponentielle linéaire. Symboliquement, notons une machine de Turing arbitraire, et , et des nombres naturels:c n 0$M$$c$$n_0$$n$

$L \in \mathbf{BestE} \Leftrightarrow$ $\quad (\exists c)(\forall M)[(L(M) = L) \Rightarrow (\exists {n_0})(\forall n > {n_0})(\forall x \in {\{0,1\}^n})[T(M(x)) \ge {2^{c|x|}}]]$

où indique le temps qu'il faut avant que s'arrête sur l'entrée .M $T(M(x))$$M$$x$

J'accepte que définir une telle classe de problèmes est très étrange, car nous exigeons que chaque machine Turing , quelle que soit sa puissance, ne puisse pas décider du langage en temps moins qu'une exponentielle linéaire.$M$

Remarquez cependant que la contrepartie polynomiale-temps ( BestP ) est naturelle, car chaque machine de Turing nécessite du tempspour au moins lire son entrée.$|x|$

PS: Peut-être, au lieu de quantifier comme "pour toutes les machines de Turing ", nous devons le limiter à certaines classes de machines de Turing prédéfinies, telles que les machines de Turing à temps polynomial. De cette façon, nous pouvons définir des classes comme , qui est la classe de langages nécessitant au moins un temps quadratique pour être décidé sur des machines de Turing à temps polynomial.B e s t ( n 2$M$$\mathbf{Best(n^2)}$

PS2: On peut également considérer l'équivalent de la complexité du circuit, dans lequel nous considérons la taille / profondeur du circuit le moins pour décider d'une langue.

Bien que je ne puisse pas vraiment analyser vos définitions, vous devez savoir que des hiérarchies temporelles beaucoup plus fortes sont connues, en particulier des hiérarchies temporelles "presque partout".

Voici l'énoncé formel: pour chaque temps lié , il existe un langage L ∈ T I M E [ T ( n ) ] avec la propriété que tout algorithme déterministe qui reconnaît correctement L doit s'exécuter dans le temps asymptotiquement supérieur à t ( n ) sur toutes les entrées, mais en nombre fini, pendant un temps suffisamment petit t ( n ) . $T(n)$$L \in TIME[T(n)]$$L$$t(n)$$t(n)$

"Suffisamment petit" signifie .$t(n) \log t(n) \leq o(T(n))$

Supposons que nous choisissons pour un exemple, et d' obtenir une langue inintelligible L . Ensuite, tout algorithme qui reconnaît correctement L doit prendre au moins 2 n / n 2 de temps sur toutes les entrées au-delà d'une certaine longueur. Cela semble être ce que vous recherchez dans votre classe BestE.$T(n)=2^n$$L$$L$$2^n/n^2$

Référence:

John G. Geske, Dung T. Huynh, Joel I. Seiferas: une note sur les ensembles presque partout complexes et la séparation des classes déterministes-complexité-temps Inf. Comput. 92 (1): 97-104 (1991)

Il existe un certain nombre de classes qui tentent d'aborder diverses notions de complexité de cas moyen. Au Complexity Zoo, certaines classes qui pourraient vous intéresser sont:

AvgP

HeurP

DistNP

(NP, échantillonnable P)

Arora / Barak couvre de nombreuses classes similaires (dans Ch 18), définissant distP, distNP et sampNP.

La relation exacte entre toutes ces classes est caractérisée par Five Worlds d'Impagliazzo, qui a déjà été posée dans une autre question .

En ce qui concerne la question de la complexité du «meilleur cas», je ne suis pas sûr de bien comprendre ce que vous voulez dire. Vous recherchez de l' EXP ?

Si vous voulez dire des classes de complexité définies en termes de meilleur temps d'exécution de cas sur toutes les instances, ce n'est pas une très bonne mesure de complexité a priori, car vous ne regarderiez que les cas triviaux d'un problème donné.

$TIME[T(n)]$$\mathcal{C}$$L$$\mathcal{C}$$L' \subseteq L$$L' \in \mathcal{C}$$L$$\mathcal{C}$$L$$\overline{L} = \Sigma^* \backslash L$$\mathcal{C}$$\mathbf{BestE}$$E$

(Mise à part historique: la notion d'immunité a été développée pour la première fois par Post en 1944 dans la théorie de la calculabilité, bien avant que P ne soit même défini. le mot «immunisé» signifie généralement «immunisé contre les ensembles calculables». Dans ce cadre, l'immunité équivaut à «immunisé contre les ensembles ce», car chaque ensemble infini ce contient un infini calculable. Je crois que l'article de Post a également été le premier à introduire le notion de réduction de plusieurs, mais je ne pouvais pas le jurer.)

Différents cas ont plus de sens lorsque l'on parle d'algorithmes, pas de problèmes. D'un autre côté, les classes de complexité concernent les problèmes, pas les algorithmes. Par conséquent, la classe de complexité étant toujours le pire des cas pour tout algorithme est due à la définition.

Dans la complexité, votre objectif est de connaître le nombre de ressources nécessaires pour résoudre n'importe quelle instance d'un problème donné. Par conséquent, vous savez que pour une instance et un algorithme donnés, vous allez avoir besoin de ces ressources et rien de plus.

Dans l'analyse d'algorithmes, votre objectif est de vous assurer que votre algorithme a une limite supérieure pour une ressource, dans n'importe quel cas du problème. Une limite triviale est la classe de complexité du problème, car aucun algorithme utile (celui qui fait des étapes inutiles) ne prend plus de temps que cela. Cependant, vous pouvez améliorer cette limite compte tenu des spécificités de l'algorithme.

$\Theta$

Quant au meilleur des cas, il est trivial pour chaque problème de trouver le moins de ressources nécessaires. Supposons que l'entrée est de longueur O (n) et la sortie de longueur O (m). Ensuite, le TM M suivant s'exécute toujours en O (n) + O (m) dans le meilleur des cas:

M {entrée, instance, solution}

1. Comparez l'instance donnée avec l'instance encodée dans la machine.
2. S'ils sont égaux, retournez la solution encodée.
3. Sinon, faites une recherche par force brute.

$O(1)$