[Solved]: Is this finite graph problem decidable? What factors make a problem decidable?

Problem Detail: 

I want to know if the following problem is decidable and how to find out. Every problem I see I can say "yes" or "no" to it, so are most problems and algorithms decidable except a few (which is provided here)?

Input: A directed and finite graph $G$, with $v$ and $u$ as vertices
Question: Does a path in $G$ with $u$ as initial vertex and $v$ as final vertex exist?

Asked By : Gigili

Answered By : Gilles

Any problem that requires only examining a finite amount of data is decidable, because there is an algorithm that consists of enumerating all the potential solutions. It may be ridiculously slow, but that's not relevant: if there is an algorithm, it's decidable.

The problem you state assumes a finite graph, which strongly hints that it's decidable. Strictly speaking, you need to look a bit further. The problem is a property on the paths in the graph, and there is sometimes an infinite number of paths, when the graph contains a cycle (you can loop around this cycle as many times as you like). However, it's easy to turn the problem to a finite problem: if there is any path beginning with $u$ and ending with $v$ that includes a cycle, then you can cut out all the cycles in that path, and you have a new solution which does not include a cycle. Since there is a finite number of paths that do not involve a cycle (if the graph has $k$ edges, there are at most $k!$ paths that do not use the same edge more than once), the problem of finding a path from $u$ to $v$ is finitary, hence decidable.

Incidentally, this property is called connectivity.

This approach is a common one, called reduction. Given a problem which is not straightforward, we reduced it to a problem we knew how to solve.

It is often difficult to prove that a problem is undecidable. To prove that a problem is decidable, all we need to do is exhibit an algorithm that decides it. To prove that a problem is undecidable, we need to prove that no algorithm can exist. There are a few well-known undecidable problems. In practice, most of the time, when we prove that a problem is undecidable, we show that there is a well-known undecidable problem that reduces to our problem. Since an algorithm for our problem would solve the well-known undecidable problem, our problem must also be undecidable.

You can't really say that "most" problems are decidable or "most" problems are undecidable. In some theoretical sense, almost all problems are undecidable, but we have a strong tendency to tackle "interesting" problems, and those are more likely to have a solution.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/143