3

Let $H$ be the language of all Turing machines that halt on empty input. Clearly $H$ is undecidable. Let $L = \{ (1,T) : T \in H \} \cup \{ (0,T) : T \not\in H \}$. Clearly $L$ is undecidable. If $L$ were decidable, then a Turing machine $M$ for $L$ would also imply the existence of a Turing machine $M'$ that decides $H$. $M'$ with input $T$ simply ...


2

An NP-complete problem is in NP, by definition. No reduction needed.


1

It follows immediately from the fact that protein folding is NP-hard that there exists a reduction from 3SAT to protein folding. The definition of NP-hard says that there is a reduction from every NP problem to protein folding; and 3SAT is a NP problem. There are papers in the literature that state that protein folding is NP-hard. I'm not an expert on ...


Only top voted, non community-wiki answers of a minimum length are eligible