<p>In some sense the halting problem satisfies this request (I was almost ready to say "There are no such examples!" when I thought of this one.) By doing diagonalization against computable sets, you can of course get sets of very high complexity, but the seemingly-most-natural way of diagonalizing against computable sets gives you a problem that is equivalent to the halting problem. As we now know, the halting problem is equivalent to many other computational problems, such as deciding many properties of TMs, telling whether a Diophantine equation has solutions, the word problem in finitely presented groups, telling whether a high-dimensional knot is the unknot, etc.</p>

<p>I am still ready to say that I would be surprised to see other examples (that aren't just, say, relativized versions of this).</p>

CC BY-SA 3.0
2014-02-08T01:34:45.213Z
2014-02-08T01:34:45.213Z
Joshua Grochow
<p>Diagonalization is a frequently used technique in complexity theory. However, the problems (sets) that are created by diagonalization rarely correspond to anything natural. It would be interesting to collect examples, when a problem was originally defined via diagonalization, but later it was found to coincide with a natural problem. </p>

CC BY-SA 3.0
2014-02-08T01:45:20.210Z
it is in a way hard to argue that any TM complete problem is any more "natural" than any other, they are equivalent and there seems to be no "natural" way of discriminating them except perhaps by # of states in the TMs etc....
vzn
CC BY-SA 3.0
2014-02-08T01:56:21.533Z
fairly close to [easy to understand undecidable problem](http://math.stackexchange.com/questions/80745/an-example-of-an-easy-to-understand-undecidable-problem), [math.se]
vzn
CC BY-SA 3.0
2014-02-08T02:05:20.460Z
similar also to [simplest TM complete system(s)](http://cstheory.stackexchange.com/questions/18233/what-are-the-simplest-turing-complete-systems) tcs.se
vzn
CC BY-SA 3.0
2014-02-08T02:17:40.177Z
@vzn: The question didn't say anything about completeness...
Joshua Grochow
CC BY-SA 3.0
2014-02-08T02:19:43.063Z
ok but it did not rule it out either as in your answer...
vzn
CC BY-SA 3.0
2014-02-08T11:13:40.197Z
Real numbers are fairly "natural", and when you use diagonalization to prove that naturals are not countable you "define" (in a loose sense) the unit interval of reals (that can be 1:1 mapped to the whole real line).
Marzio De Biasi
<cc.complexity-theory><complexity-classes>
Natural problem arising from diagonalization?
Andras Farago
# Natural problem arising from diagonalization?

(Asked by: username_0 on 2014-02-08)

Diagonalization is a frequently used technique in complexity theory. However, the problems (sets) that are created by diagonalization rarely correspond to anything natural. It would be interesting to collect examples, when a problem was originally defined via diagonalization, but later it was found to coincide with a natural problem.

**Tags:** cc.complexity-theory, complexity-classes

> **Comments:**
> **username_1**: it is in a way hard to argue that any TM complete problem is any more "natural" than any other, they are equivalent and there seems to be no "natural" way of discriminating them except perhaps by # of states in the TMs etc....  
> **username_1**: fairly close to [easy to understand undecidable problem](http://math.stackexchange.com/questions/80745/an-example-of-an-easy-to-understand-undecidable-problem), [math.se]  
> **username_1**: similar also to [simplest TM complete system(s)](http://cstheory.stackexchange.com/questions/18233/what-are-the-simplest-turing-complete-systems) tcs.se  
> **username_2**: @username_1: The question didn't say anything about completeness...  
> **username_1**: ok but it did not rule it out either as in your answer...  
> **username_3**: Real numbers are fairly "natural", and when you use diagonalization to prove that naturals are not countable you "define" (in a loose sense) the unit interval of reals (that can be 1:1 mapped to the whole real line).  

---

## 1 answers

### Answer by username_2 on 2014-02-08. Score: 7 | Accepted answer

In some sense the halting problem satisfies this request (I was almost ready to say "There are no such examples!" when I thought of this one.) By doing diagonalization against computable sets, you can of course get sets of very high complexity, but the seemingly-most-natural way of diagonalizing against computable sets gives you a problem that is equivalent to the halting problem. As we now know, the halting problem is equivalent to many other computational problems, such as deciding many properties of TMs, telling whether a Diophantine equation has solutions, the word problem in finitely presented groups, telling whether a high-dimensional knot is the unknot, etc.

I am still ready to say that I would be surprised to see other examples (that aren't just, say, relativized versions of this).


---

