Part -1:
1. Suppose you are studying the computational complexity of a given problem X. It is known that the boolean [4] satishability problem can be reduced to X in polynomial time. In addition, it is known that problem X is in class PSPACE, as somebody has developed an algorithm for X that is guaranteed to consume no more than polynomial amount of space. How would you prove that:
(a) X is NP-COMPLETE.
(b) X is PSPACE-Complete.
Observe that you do not need to develop any proof, but just explain briefly what task would you do.
2. Let X1 and X2 be two decision problems. Suppose it is known that X1 is NP-COMPLETE. Suppose further that there exists an exponential reduction of problem X1 into problem X2, that is, there exists a function f :X1 → X2, whose implementation runs in exponential time, such that for any given instance x1 of X1 the answer to x1 is "Yes" for problem X1 if and only if the answer to f(x1) is "Yes" for problem X2. 'What can be said about the computation complexity of the problem X2. Is X2 NP-HARD? Explain in one or two paragraphs.
Part -2:
2. Explain the phase transition phenomenon observed in 3-SAT.
You're expected to submit between 400 and 500 words (excluding references).
Think of it, as if you were hired to write a textbook for Computer Science undergraduates who are taking Computing Theory.
Besides providing enough technical information, your text needs to be enjoyable to read (or else the book will not sell well!). Make sure you use multiple paragraphs, correct English grammar and spelling, and language of appropriate formality with an adequate flow.
You must not copy and paste a single sentence from the web (this includes Wikipedia). Note that copied sentences are trivial to identify, so you should re-phrase in your own words whatever you read. You should also reference the material you used for your research.
Filially, we strongly recommend you proof-read your text, reflect on whether the reader (e.g.. a fellow student) would be satisfied with what you wrote and revise accordingly.