How to prove NP-hardness of CIRCUIT-SAT, without the use of other NP-complete problems but using Turing machines?
And, if it is possible, I need a full proof, not a sketch.
Asked
Active
Viewed 48 times
0
-
These lecture notes might be useful – Winther Sep 22 '15 at 22:17
-
@Winther I have already read them. And they did not help. – yhn112 Sep 22 '15 at 22:44
-
Then I suggest you find yourself a good book on the subject or perhaps there is something free on the web (try searching for proofs of Cook’s theorem). I doubt anyone will type up a proof for you here. Also a better place to ask questions of this kind is Theoretical Computerscience SE – Winther Sep 22 '15 at 23:05