[Solved]: What kind of reductions are usually used in order to prove PP-completeness?

Problem Detail: 

I've read that MAJSAT is PP-complete. Under what type of reduction is this true? What kind of reductions are usually used in order to prove PP-completeness?

Asked By : Fayez Abdlrazaq Deab

Answered By : D.W.

Here "PP-complete" means "complete for PP". The definition of PP defines the complexity class PP; it does not define the type of reduction you can use, as that is an orthogonal concern. So, "complete for PP" actually means "complete with respect to a particular class of reductions", and the meaning of that is implicitly parametrized by a class of reductions (usually the reader assumes you will be able to infer the class, from context). For each class of reductions, you potentially get a different notion of completeness.

In this case, we're talking about polynomial-time many-one reductions, also known as Karp reductions -- the same class of reductions as is commonly used in the definition of NP-completeness. This becomes immediately clear if you read the proof of completeness of MAJSAT (it's immediate to see that this is the type of reduction that gets constructed, in that proof).

In the future, please make sure to do research through standard sources before asking here, and to use some effort to formulate your question clearly and precisely -- that will increase the chances that you get a useful answer.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14528

3.2K people like this

 Download Related Notes/Documents