Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.