Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
CS 262: Computational Complexity Homework 1
1. The definition of 3SAT allows for clauses to have fewer than three literals. We will define a resticted version of 3SAT called EXACT-3SAT in which the literals in each clause must be distinct and every clause must have exactly three literals. (Recall that a literal is a variable or the negation of a variable). Prove that 3SAT reduces to EXACT-3SAT.
2. Prove that there exist functions which are not proper.
3. A complexity class C is said to be closed under reductions if whenever L reduces to L 0 and L 0 ∈ C, then L ∈ C. Prove that P and PSPACE are closed under reductions. Is TIME(n 2 ) closed under reductions? Justify your answer.
4. Show that one of the following inequalities must hold: L 6= P or PSPACE 6= P. Note that both are believed to be true, and no one knows how to prove either one.