1
$\begingroup$

I recently noted from http://rjlipton.wordpress.com/2010/11/07/what-is-a-complexity-class/ that a problem is defined as a mere set of strings.

So, here is the point: If I say the following: "Find whether there is a path between vertex x and vertex y", how then are these strings combined into a problem? Can a control string be used as a string?

1 Answers 1

1

There are two ways to formalize that problem.

If we are interested in finite graphs, we would define the problem to be a set of some triples of the form $(G, x, y)$ where $G$ is a (description of a) finite graph and $x, y$ are vertices in $G$. By picking some effective coding system, we can view each of these triples as a string or as a single natural number. The "problem" would then be defined formally as the set of triples $(G, x, y)$ such that there is a path from $x$ to $y$. This problem is decidable - there is an algorithm to tell whether a triple is in the set - but the question would be what subrecursive complexity class the problem lies in.

If we are interested in infinite graphs, we do something slightly different. For a fixed infinite (countable) graph $G$ there is a problem $P_G$ consisting of all pairs $(x,y)$ of vertices of $G$ such that there is a path from $x$ to $y$. For some graphs this problem is decidable, and for some it is not; in general we would be interested in how uncomputable the problem $P_G$ is in terms of the level of uncomputability of $G$ itself.

Both of these descriptions are correct on the large scale but leave out some details, which would be covered in depth in a book on computability.