Est-ce problème graphe fini décidable? Quels facteurs font un décidable problème?

Question

Je veux savoir si le problème suivant est décidable et comment trouver. Chaque problème que je vois, je peux dire « oui » ou « non », donc la plupart des problèmes sont et les algorithmes décidable sauf quelques (qui est fourni )?

  

Entrée: A dirigé et fini graphe $ G $, avec $ v $ et $ u $ en tant que sommets
  Question: Est-ce un chemin dans $ G $ avec $ u $ au sommet initial et $ v $ comme exist de sommet final

Answer 1

Tout problème qui nécessite d'examiner seulement une quantité limitée de données est décidable, car il existe un algorithme qui consiste à énumérer toutes les solutions possibles. Il peut être ridiculement lent, mais ce n'est pas pertinente. S'il y a un algorithme, il est décidable

Le problème que vous l'état suppose un graphe fini, ce qui laisse deviner fortement qu'il est décidable. A proprement parler, vous avez besoin de regarder un peu plus loin. Le problème est une propriété sur les chemins dans le graphique, et il y a parfois un nombre infini de chemins, lorsque le graphe contient un cycle (vous pouvez boucle autour de ce cycle autant de fois que vous le souhaitez). Cependant, il est facile de tourner le problème à un problème fini: s'il y a un chemin en commençant par $ u $ et se terminant avec $ v $ qui comprend un cycle, vous pouvez découper tous les cycles dans cette voie, et vous avez un nouvelle solution qui ne comprend pas un cycle. Comme il y a un nombre fini de chemins qui ne comportent pas un cycle (si le graphique a $ k arêtes $, il y a au plus k $! Chemins $ qui n'utilisent pas le même bord plus d'une fois), le problème de trouver un chemin de $ u $ à $ $ v est finitaire, donc décidable.

Soit dit en passant, cette propriété est appelée connectivité .

Cette approche est commune, appelée réduction . Face à un problème qui n'est pas simple, nous avons réduit à un problème que nous savions comment résoudre.

Il est souvent difficile de prouver qu'un problème est indécidable. Pour prouver qu'un problème est décidable, tout ce que nous devons faire est exposer un algorithme qui décide. Pour prouver qu'un problème est indécidable, nous devons prouver qu'aucun algorithme ne peut exister. Il y a quelques problèmes indécidables bien connus. Dans la pratique, la plupart du temps, quand nous montrons qu'un problème est indécidable, nous montrons qu'il ya un problème indécidable bien connu qui réduit à notre problème. Depuis un algorithme de notre problème résoudrait le problème indécidable bien connu, notre problème doit également être indécidable.

Vous ne pouvez pas vraiment dire que « la plupart » des problèmes sont décidables ou les problèmes sont indécidables « la plupart ». Dans un certain sens théorique, presque tous les problèmes sont indécidables, mais nous avons une forte tendance à aborder les problèmes « intéressants », et ceux qui sont plus susceptibles d'avoir une solution.

Answer 2

Le problème est trivialement décidable, comme l'a souligné Gilles dans un commentaire. Quant à votre autre question ...

  

sont la plupart des problèmes et des algorithmes décidable sauf quelques (qui est fourni )?

Non. En fait, la plupart problèmes sont indécidables. En fait, il y a beaucoup de problèmes indénombrablement (langues), mais il n'y a que beaucoup dénombrable machines de Turing, ce qui signifie qu'il ya au plus dénombrables de nombreux problèmes décidables.

Answer 3

Oui, cela est décidable, parce que vous pouvez faire une recherche exhaustive de tous les chemins possibles. Il n'y a pas besoin de regarder tous les chemins qui se répètent d'un sommet, puisque le « détour » pourrait être sautée. Mais la longueur de tout chemin non répétitif est limitée par la taille du graphique, ce qui est fini, et donc il n'y a que beaucoup de ces chemins finiment, qui peuvent être vérifiés un par un.

Qu'est-ce pas décidable est la suivante: étant donné un graphe infini $ G $ et deux sommets $ a et $ b $, décider s'il y a un chemin de $ a $ à $ b $. Ce n'est pas décidable si le graphe est donnée comme un oracle et est pas non plus décidable si le graphe est donné au moyen d'un programme qui calcule lui.

Answer 4

Il n'y a pas de méthode qui vous indique si un problème spécifique est décidable ou non. Avec le temps, vous pourriez obtenir un bon « intuition » si oui ou non un problème spécifique est décidable.

Ce que je fais habituellement est le suivant:

1. essayer de résoudre le problème. C'est, essayez de penser à un programme informatique qui permet de résoudre le problème donné. Pour votre problème suggéré - un programme très simple va vérifier tout simplement chemin possible et donc réussira toujours à trouver (si elle existe), ou vous dire pas de chemin existe autrement.
2. formuler clairement le problème. De nombreux problèmes sont trop vagues, mais lorsqu'il est écrit clairement il est très facile de voir si décidable ou non (en comparant à d'autres problèmes, connus pour être un / décidable, ou en utilisant des méthodes connues comme Rice's théorème )
3. Si (2) n'a pas fonctionné, mais vous croyez encore le problème est indécidable, essayez de le prouver par la réduction d'un problème indécidable (problème de l'arrêt (ou son complément) travaille pour de nombreux cas).

Presque toujours, en essayant de faire l'étape (1) pour un problème indécidable, vous aurez besoin de votre programme pour vérifier infini nombre de choses. Cela est généralement un signe que le problème n'est pas décidable.