snippetMinor
How do I prove Berman's theorem?
Viewed 0 times
provebermantheoremhow
Problem
Berman's theorem states
If a unary language ( a language with all the strings of the type $1^i$, $ i > 0 $ ) is NP-Complete then P = NP.
I tried reducing SAT to a given unary language $L$ assuming it is NP-Complete. But I can't think of a way such that after applying the reduction so that SAT gets solved in polynomial time. How do I proceed further?
This is an exercise from Sanjeev Arora and Boaz Barak , but not homework.
If a unary language ( a language with all the strings of the type $1^i$, $ i > 0 $ ) is NP-Complete then P = NP.
I tried reducing SAT to a given unary language $L$ assuming it is NP-Complete. But I can't think of a way such that after applying the reduction so that SAT gets solved in polynomial time. How do I proceed further?
This is an exercise from Sanjeev Arora and Boaz Barak , but not homework.
Solution
Please refer this solution. Or see the paper by S. R. Mahaney, Sparse complete sets for NP: Solution of a conjecture by Berman and Hartmanis (Journal of Computer and System Sciences, 25:130-143, 1982).
Context
StackExchange Computer Science Q#53268, answer score: 4
Revisions (0)
No revisions yet.