Est-il possible d'estimer la RAM nécessaire de la complexité de l'espace Turing?

Question

Les machines de Turing peut considérer la complexité dans l'espace (espace mémoire sur bandes) et le temps.

Il y a des classes telles que PSPACE et EXPSPACE.

De plus, nous pouvons présenter des algorithmes qui sont certainement PSPACE.

http://www.springerlink.com/content/3hqtq11mqjbqfj2g/

Cependant, quand je fait des programmes de code, certains programmes fonctionnent plus rapidement que d'autres, certains programmes ont une plus petite mémoire (RAM) empreinte que d'autres.

On peut supposer que si le code I un algorithme PSPACE pour résoudre le problème X et aussi un algorithme de EXPSPACE pour résoudre le même problème, le programme EXPSPACE devrait utiliser beaucoup plus de RAM que le code PSPACE.

Est-il possible d'estimer la quantité de RAM seront impliqués, selon la cote théorique de l'algorithme de départ?

Answer 1

En principe, non. Dans la pratique, parfois.

D'abord, vous devez comprendre ce que l'analyse de la complexité en fait des moyens (examiner les définitions dans votre manuel). PSPACE signifie simplement que l'espace nécessaire est délimitée par une fonction polynomiale de la taille d'entrée. Il ne vous dit pas ce que la fonction de délimitation est, ou ce que l'espace réel utilisé est. Donc, vous ne pouvez pas travailler quoi que ce soit sur la RAM juste en connaissant un algorithme est PSPACE.

Si vous savez qu'un algorithme est PSPACE, vous pourriez émettre l'hypothèse que l'espace qu'il utilise est non seulement borné par un polynôme, il est décrit par un polynôme. Il pourrait ne pas être vrai, mais pour de nombreux algorithmes, il est vrai. Vous pouvez ensuite calculer (ou mesure) l'espace utilisé pour différentes tailles d'entrée différentes, et essayer de faire correspondre un polynôme aux données.

En général qui est assez inutile (parce que sans connaître l'ordre du polynôme, il existe une infinité de crises possibles). Mais dans la pratique, si vous savez que l'espace utilisé est, par exemple O (n), et vous avez une idée de ce genre d'entrée produiront l'utilisation de l'espace le plus défavorable, alors vous pouvez faire des prévisions assez précises. Si cela prend 10 Mo de RAM pour traiter 1Mo d'entrée, et 20 Mo de RAM pour traiter 2MB d'entrée, puis souvent, il faudra environ 100 Mo de RAM pour traiter 10MB d'entrée. Mais vous gagnerez seulement cette idée de la connaissance plus détaillée de l'algorithme que simplement savoir qu'il a la complexité de l'espace polynomiale.

Answer 2

  

On peut supposer que si le code I un algorithme PSPACE pour résoudre le problème X et aussi un algorithme de EXPSPACE pour résoudre le même problème, le programme EXPSPACE devrait utiliser beaucoup plus de RAM que le code PSPACE.

Vous présumez pas.

Ces classes de complexité décrivent la croissance asymptotique de mémoire requise pour exécuter l'algorithme. Ils vous disent absolument rien au sujet de la quantité réelle de RAM nécessaire.

En fait, pour une taille de problème n , au-dessus de cette taille EXPSPACE utilisera plus de mémoire que PSPACE, mais pour quoi que ce soit en dessous de n , vous ne pouvez pas vraiment dire quoi que ce soit (comme O (n ² ) algorithmes pourraient exécuter des algorithmes plus rapides que O (n) pour les petites n ).