<p>No.</p>

<p>Turing-recognizable undecidable languages can be <strong>unary</strong> (define $x \not\in L$  unless $x = 0000\ldots 0$, so the only difficult strings are composed solely of 0's). Mahaney's theorem says that no unary language can be NP-complete unless P=NP. </p>

CC BY-SA 3.0
2013-01-22T17:02:51.847Z
Thanks for the answer and the useful pointer to Mahaney's theorem!
veryltdbeard
CC BY-SA 3.0
2013-01-22T16:48:02.267Z
2013-01-22T16:48:02.267Z
Peter Shor 
<p>Does every Turing-recognizable undecidable language have a NP-complete subset?</p>

<p>The question could be seen as a stronger version of the fact that every infinite Turing-recognizable language has an infinite decidable subset.</p>

<cc.complexity-theory><np-hardness><complexity-classes><np><decidability>
Does every Turing-recognizable undecidable language have a NP-complete subset?
veryltdbeard
# Does every Turing-recognizable undecidable language have a NP-complete subset?

(Asked by: username_0 on 2013-01-22)

Does every Turing-recognizable undecidable language have a NP-complete subset?

The question could be seen as a stronger version of the fact that every infinite Turing-recognizable language has an infinite decidable subset.

**Tags:** cc.complexity-theory, np-hardness, complexity-classes, np, decidability

---

## 1 answers

### Answer by username_1 on 2013-01-22. Score: 22 | Accepted answer

No.

Turing-recognizable undecidable languages can be **unary** (define $x \not\in L$ unless $x = 0000\ldots 0$, so the only difficult strings are composed solely of 0's). Mahaney's theorem says that no unary language can be NP-complete unless P=NP.

> **Comments:**
> **username_0**: Thanks for the answer and the useful pointer to Mahaney's theorem!  

---

