1. If a language L is Turing-recognizable, must it be Turing-decidable? If it is Turing-decidable, must it be Turing-recognizable? Justify your answer.
2. Let L∗ be the language that contains strings ⟨M,N⟩ in which M and N are Turing machines such that L(M) = L(N). Show that L∗ is not Turing-recognizable.
3. Given languages A and B, let A ⊕ B = {w : w is in exactly one of A and B}.
(a) Are Turing-decidable languages closed under the ⊕ operator? Justify your answer.
Copyright By PowCoder代写 加微信 powcoder
(b) Are Turing-recognizable languages closed under ⊕? Justify your answer.
4. Give a language that is NP-hard but is not in NP. Justify your answer.
5. Given an integer m × n matrix A and an integer m-vector b, the 0-1 integer programming problem asks whether there exists a {0, 1}-valued n-vector x such that Ax ≥ b (meaning that the m-vector Ax is entry-wise bounded from below by b). Show that the problem is NP-complete. (Hint: Reduction from 3SAT.)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com