Est-il possible de décider si un algorithme donné est asymptotiquement optimal?

Existe-t-il un algorithme pour le problème suivant:

Étant donné une machine de Turing qui décide d'un langage , existe-t-il une machine de Turing décidant telle que ? $M_1$ $L$
$M_2$ $L$ $t_2(n) = o(t_1(n))$

Les fonctions et sont respectivement les durées de fonctionnement les plus défavorables des machines Turing et . $t_1$ $t_2$ $M_1$ $M_2$

Et la complexité de l'espace?

complexity-theory computability undecidability decision-problem StaticBug
la source

La réponse n'est certainement pas. La détermination du temps d'exécution le plus défavorable d'une MT est connue pour être indécidable.

chazisop

Question plus générale .

Raphael

Réponses:

Voici un argument simple pour montrer qu'ils sont indécidables, c'est-à-dire qu'il n'y a pas d'algorithmes pour vérifier si un algorithme donné est optimal en ce qui concerne son temps d'exécution ou l'utilisation de la mémoire.

Nous réduisons le problème d'arrêt sur bande vierge à votre problème d'optimalité de la durée d'exécution.

Soit une machine de Turing donnée. Soit N la machine de Turing suivante: $M$

$N$ : sur l'entrée 1. Exécutez sur une bande vierge pendant (au plus) étapes. 2. Si ne s'arrête pas en étapes, exécutez une boucle de taille , puis retournez NO. 3. Sinon, retournez OUI. $n$
$M$ $n$
$M$ $n$ $2^n$

Il y a deux cas:

Si ne s'arrête pas sur une bande vierge, la machine s'exécutera pour les étapes sur l'entrée . Son temps d'exécution est donc . Dans ce cas, n'est évidemment pas optimal. $M$ $N$ $\Theta(2^n)$ $n$ $\Theta(2^n)$ $N$
Si s'arrête sur une bande vierge, alors la machine s'exécutera pour un nombre constant d'étapes pour tous les suffisamment grands , donc le temps d'exécution est . Dans ce cas, est évidemment optimal. $M$ $N$ $n$ $O(1)$ $N$

En bref:

M halts on blank tape \Leftrightarrow N is optimial

$M \text{ halts on blank tape } \Leftrightarrow N \text{ is optimial }$

De plus étant donné le code pour on peut calculer le code pour . Par conséquent, nous avons réduit le problème d'arrêt sur bande vierge en un problème d'optimalité au moment de l'exécution. Si nous pouvions décider si une machine de Turing donnée est optimale, nous pourrions utiliser la réduction ci-dessus pour vérifier si une machine donnée s'arrête sur du ruban vierge. Étant donné que l'arrêt sur une bande vierge est indécidable, votre problème est également indécidable. $M$ $N$ $N$ $M$

Un argument similaire peut être utilisé pour l'espace, c'est-à-dire qu'il est également indécidable de vérifier si une machine de Turing donnée est optimale en ce qui concerne l'espace qu'elle utilise.

Même une affirmation plus forte est vraie: nous ne pouvons pas décider si une fonction calculable donnée est une limite supérieure de la complexité temporelle du calcul d'une fonction calculable donnée. De même pour l'espace. C'est-à-dire que même la théorie de la complexité de base ne peut pas être automatisée par des algorithmes (ce qui peut être considéré comme une bonne nouvelle pour les théoriciens de la complexité;).

Kaveh
la source

Je veux juste mentionner que dans la question initiale, OP a supposé que décide de la langue en temps quadratique.

M_{1}

$M_1$

Pål GD

Veuillez préciser que vous regardez l' optimalité asymptotique . Même dans le cas 2, n'est pas strictement optimal; la fonction peut être calculée en une seule étape, alors que besoin de plus de (pour les grands ), avec la longueur du calcul de sur bande vierge.

n

$n$

n \mapsto YES

$n \mapsto \textrm{YES}$

N

$N$

n_{0}

$n_0$

n

$n$

n_{0}

$n_0$

M

$M$

Raphael

Ah, la question a changé depuis ma dernière lecture. Ça ne fait rien.

Raphael

@ PålGD, je pense que OP a utilisé cela comme exemple (basé sur la question originale publiée sur cstheory). Vous pouvez vérifier les commentaires sous cette question.

Kaveh

Comme d'autres l'ont mentionné, la réponse est non.

Mais il y a un article intéressant écrit par Blum " Une théorie indépendante de la machine de la complexité des fonctions récursives ". Il a montré qu'il existe certaines fonctions avec la propriété que peu importe la vitesse à laquelle un programme peut être pour calculer ces fonctions, un autre programme existe pour les calculer beaucoup plus rapidement .

une très belle propriété!

Reza
la source

-3

Ha! Si la réponse était oui, nous vivrions dans un monde différent.

$A_0$ $A$ $L$ $A_0$ $A$

Malheureusement, ce n'est pas possible, et en effet je pense personnellement que prouver l'optimalité (non triviale) est le problème le plus intéressant (et le plus difficile) en informatique. Pour autant que je sache - je serais heureux d'être corrigé - il n'existe aucun résultat d'optimalité pour un problème polynomial (à l'exception des résultats d'optimalité triviaux bien sûr des algorithmes prenant un temps proportionnel à la taille d'entrée).

t au t
la source

Ω (N)

$\Omega(N)$

Ω (n \log n)

$\Omega(n \log n)$

@vonbrand - c'est ce que je voulais dire par algorithmes prenant proportionnellement à la taille d'entrée.

au t

@ttothet D'accord, j'ai bien peur que ce soit infructueux mais je vais réessayer. 1) Non, pas du tout. Si vous enregistrez une seule étape sur chaque entrée, vous disposez d'un meilleur algorithme qu'auparavant, même s'il a le même temps d'exécution asymptotique. 2) Non, ce n'est pas le cas. Cela peut aussi signifier "je ne sais pas, mais si oui, alors X". Ce n'est pas rare (cf. P? = NP). 3) Vous avez demandé il n'y avait pas que je suppose minorations non trivial (sur asymptote,) du tout . C'est faux. Faites vos devoirs, s'il vous plaît.

Raphael

@ MartinJonáš Je veux dire une machine de Turing à 2 bandes. Kaveh a raison, la preuve du théorème de la hiérarchie temporelle donne des problèmes résolus par les polytimes avec une complexité arbitrairement élevée, mais les exemples ne sont pas exactement naturels et ne semblent pas très explicites. De plus, aucune hiérarchie n'est connue pour le temps probabiliste, donc nous n'avons vraiment rien.

Sasho Nikolov