Simulation développements et discussion

La complexité est une théorie qui repose sur la classification de problèmes en diffé- rentes classes. Le type de problème le plus commun et le plus étudié est le problème de décision. Un tel problème pose une question à laquelle on doit répondre soit par « oui », soit par « non ». L’ensemble des questions que l’on peut poser sont les instances du problème, qui sont dites positives lorsque la réponse est « oui », et négatives lorsque la réponse est « non ». En général, les instances sont considérées comme des nombres plutôt que des phrases ; il est simple de voir que l’on peut toujours transformer l’un en l’autre. Nous faisons dans ce chapitre la comparaison entre la réduction et la simulation. Ces deux opérations visent à démontrer que l’on peut résoudre un objet en en utilisant un autre, en permettant une mesure de complexité. Nous sommes intéressés à pousser l’analogie le plus loin possible, pour comprendre quelles structures sont conservées dans la traduction, et lesquelles sont transformées. Nous supposons la définition de simulation développée en section 2.3.2 car, bien qu’elle soit incomplète, elle reste la définition la plus satisfaisante. Pour rappel, la définition de réduction est donnée en section 1.8, accompagnée des autres définitions de base liées à la théorie de la complexité.

La première différence entre réduction et simulation est que les objets sur lesquels ces notions opèrent sont fondamentalement différents : les problèmes disposent toujours d’un nombre infini d’instances, et la difficulté de ces problèmes repose uniquement sur la répartition des réponses positives à ces instances. Un système de transition d’états est bien plus libre dans sa structure ; un tel système peut à priori être de toute taille, même finie, et peut inclure des chemins infinis lorsqu’il est infini. ! o si et seulement si i est une instance positive de taille n, et i de l’instance. Cela permet à la fonction g de décider du temps nécessaire à attendre pour résoudre une instance donnée. Cette façon de traduire un problème de décision peut paraître artificielle, et témoigne des différences entre problèmes de décision et systèmes de transition d’états. Pour traduire les problèmes en systèmes, certaines technicités sont nécessaires.La définition des classes de complexité repose sur la résolution de problèmes par des machines limitées en temps et en espace. Nous construisons une analogie basée sur la simulation en remplaçant la condition de résoudre le problème par une machine par la condition que le système étudié soit simulable par la même machine disposant des mêmes restrictions.

Nous faisons l’observation importante que, telle que décrite dans ces définitions, chaque configuration de ces systèmes de transition d’états contient l’information d’un vecteur bi-infini dans ¤ . Cette observation est problématique puisque ce vecteur passe par définition en entrée et sortie des fonctions qui composent une simulation polynomiale. Si ces entrées et sorties sont infinies, la question d’une mesure de com- plexité devient inapplicable. Pour contourner ce problème, nous considérons que ce ruban peut être alternativement défini comme la liste des positions dont l’état n’est pas 0, pour 0 un état arbitraire de ¤. Cet encodage permet de définir la simula- tion d’un modèle à description finie par une machine de Turing, et de mesurer cette simulation en complexité sous l’hypothèse que les configurations employées dans cette simulation comportent toutes un nombre fini de positions dont la valeur n’est pas 0. Il n’est cependant pas difficile de voir que cette hypothèse est conservée dans l’ensemble des simulations considérées dans ce chapitre.) vaudra o si la machine est dans un état final acceptant, et p si la machine est dans un état final de refus. Cette fonction est calculable en espace logarithmique ; d’abord, dans le cas d’un état final , la fonction est calculable en temps constant. Dans le cas d’une configuration initiale, on considère que h répond simplement l’instance rédigée dans le ruban de la machine dans son état initial, ce qui est clairement calcu- lable en espace logarithmique. Cela fonctionne car on considère que toute instance mal formée du problème A est une instance négative du problème A. Grâce à cette hypothèse, h admet toute configuration initiale de la machine dans son domaine, et chaque instance de A est transformée en exactement une configuration initiale. Autrement dit, la charge de la preuve que i est une instance bien formée est laissée à la machine de Turing T plutôt qu’à h.