Déterminisme et équations de Riccati

a marqué ce sujet comme résolu.

Hello,

On a vu dans deux cours différents deux notions différentes :

  • Le déterminisme des machines de Turing et son symétrique le non déterminisme, qui grâce a un oracle peut résoudre un problème quelconque en un temps constant 1. On peut voir qu'une machine non déterministe peut être ramenée à une machine déterministe, elles calculent la même chose 2.
  • Les équations de Ricatti qui sont résolvables si on possède une solution particulière 3. Je n'ai pas trouvé de moyen de les résoudre dans tout les cas sans cette solution particulière 4.

Vous voyez où je veux en venir. Le choix de la solution particulière de l'équation de Riccati ressemble fortement à un oracle. On devrait donc pouvoir résoudre une équation de Riccati de façon déterministe dans tout les cas.

Quelqu'un saurait-il comment lever cette contradiction ?

PS : Il semblerait que la 4ème URL ait un bug à l'affichage.

  1. http://fr.wikipedia.org/wiki/Oracle_%28machine_de_Turing%29 ↩

  2. http://fr.wikipedia.org/wiki/Machine_de_Turing_non_d%C3%A9terministe#Impact_sur_le_temps_de_calcul ↩

  3. http://fr.wikipedia.org/wiki/%C3%89quation_de_Riccati ↩

  4. http://www.les-mathematiques.net/phorum/read.php?4,643870,644008 ↩

+0 -0

Salut,

Je ne suis pas spécialiste du domaine, donc ma remarque est peut être parfaitement idiote.

En fait, je ne vois pas le lien entre machine avec oracle et machine non-déterministe. Pour moi, ce sont deux concepts différents. Tu peux très bien considérer une machine déterministe avec oracle, je ne vois pas le problème. Et du coup, ça lèverait ton paradoxe. Une machine non-déterministe avec oracle calcule la même chose qu'une machine déterministe avec oracle. La machine avec oracle peut résoudre un problème indécidable quelconque, ce qui n'est évidemment pas le cas d'une machine sans oracle, qu'elle soit déterministe ou non.

+0 -0

+1 pour @dri1. Je ne connais pas les équations de Ricatti dont tu parles, mais il semble que tu confondes machine avec oracle et machine non-déterministe, qui sont deux notions bien différentes.

Une machine est déterministe si, dans un état donné et sur un caractère donné, il n'existe qu'une seule transition possible. Une machine non déterministe peut avoir plusieurs transitions possibles dans ce cas, et donc explorer plusieurs possibilités simultanément. Elle ira "plus vite". Cette notion sert à définir la classe de complexité NP qui correspond à l'ensemble des problèmes qu'une machine non-déterministe peut résoudre en un temps polynomial. On montre qu'une machine déterministe sait résoudre les mêmes problèmes.

En revanche, la notion d'oracle permet elle de résoudre des problèmes indécidables en temps constant. On ne parle plus de complexité, mais de calculabilité.

+0 -1

Effectivement je me suis embrouillé sur la définition de déterminisme.

Pour revenir aux équations de Riccati, vu qu'il faut faire un choix de solution initiale, qu'est ce qui empêche d'utiliser une machine indéterministe pour l'obtenir ? (quitte a simuler cette machine de façon déterministe plus tard).

+0 -0

Pour revenir aux équations de Riccati, vu qu'il faut faire un choix de solution initiale, qu'est ce qui empêche d'utiliser une machine indéterministe pour l'obtenir ?

Ben… Le fait que ce n'est pas un problème décidable.

+0 -0

Question très intéressante.

Il est en effet impossible de faire résoudre sans apport de la solution initiale une équation de Riccati de manière déterministe aujourd'hui, à ma connaissance. Ce qui signifie donc, qu'effectivement, aujourd'hui ce n'est pas un problème indécidable1, vocabulaire non adapté, mais un problème NP-Complet (voir plus bas).

@dri1, le rapport entre oracle et machine non-déterministe c'est que justement, un problème peut être résolu par une machine de Turing non déterministe s'il existe un Oracle tel qu'il existe un algorithme polynomial permettant de résoudre ce problème à l'aide de l'Oracle. Rappelons que la classe NP ne veut pas dire Non-Polynomial mais Non déterministe polynomial.
De fait, le problème de résoudre Ricatti est bien un problème qui peut être résolu par une machine de Turing non-déterministe car étant donnée l'Oracle, une solution initiale, le calcul de la solution peut se faire en tant polynomial (par exemple par une formule de quadrature, non applicable sans la solution initiale).

@Bibibye, non. Une machine de Turing possédant un noyau de transition est une machine de Turing probabiliste (oui, je sais le vocabulaire est très à chier). Mais tu as un peu tout mélangé dans ton poste. :/ Et d'ailleurs, pour te montrer que cela n'a rien à voir avec la décidabilité: « Le concept de machine de Turing non déterministe n'étend pas la notion de calculabilité et ainsi les machines de Turing non déterministes calculent exactement les mêmes fonctions que les machines de Turing déterministes, car une machine de Turing non déterministe peut être simulée par une machine de Turing déterministe. »

  1. A ma connaissance on n'a pas montré qu'il n'était pas possible de trouver un algorithme permettant de retourner une solution initiale. A ce jeu là, je parie même qu'on pourrait montrer l'inverse sur des domaines de définition particulier. ↩

+1 -0

Quit à me faire un peu de publicité, tu trouveras quelques informations connexes, dont des définitions précises sur les classes de complexités (en tout cas les deux plus communes, mais le principe étant plutôt de montrer sur quelles types de relation elles sont basées) ici.

L'article serait aujourd'hui à peaufiner et compléter (j'ai au moins 3 idées d'ajouts pertinents pour les exemples d'erreurs ou de mauvaise compréhension de la complexité en temps), mais la première partie n'est pas à jeter.

+0 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte