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?

  • $\begingroup$ What have you tried? Have you looked in Wikipedia? Have you looked in a complexity theory textbook? In the complexity zoo? $\endgroup$ – D.W. Sep 23 '13 at 7:07
  • $\begingroup$ @D.W. I am familiar with several books that deals with complexity theory , but non of them mention these things , also in Wikipedia nothing mentioned about the definition ... $\endgroup$ – Fayez Abdlrazaq Deab Sep 23 '13 at 19:02
  • $\begingroup$ Fayez, Wikipedia does have a definition of how the PP complexity class is defined: appropriately enough, in the article on PP. It also has a link to the complexity zoo article on PP. That should answer your question about how the PP class is defined. Generally, folks here expect you to do some research before asking here and to show what research you've done in your question. See also cs.stackexchange.com/questions/how-to-ask and meta.cs.stackexchange.com/q/89/755 $\endgroup$ – D.W. Sep 23 '13 at 19:32
  • $\begingroup$ P.S. I don't know what "where this problems are good?" means. I encourage you to edit your question to ask a more precisely defined question (click the "edit" button underneath). $\endgroup$ – D.W. Sep 23 '13 at 19:33

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.

| cite | improve this answer | |
  • $\begingroup$ Neither Wikipedia nor the complexity zoo mention which reductions are meant. I would guess polytime many-one reductions, but as you say, the only way to be sure is look at a paper formally defining this concept (such as the MAJSAT-completeness proof). It could also be the case (as in other situations) that the concept stays the same under several different definitions of reductions. $\endgroup$ – Yuval Filmus Sep 23 '13 at 19:58
  • $\begingroup$ In conclusion, I don't think the question is completely obvious. For one, I think you should amend the Wikipedia article with this information, since it just isn't there. $\endgroup$ – Yuval Filmus Sep 23 '13 at 19:59
  • $\begingroup$ I dont know where "somebody" prove that MAJSAT is PP complete so I asked this question here ... so as you say this class is closed under polynomial reductions ? this fact should be obvious ? $\endgroup$ – Fayez Abdlrazaq Deab Sep 23 '13 at 21:54
  • $\begingroup$ @FayezAbdlrazaqDeab, can you explain what it would mean to say "PP is closed under polynomial reductions"? I'm not familiar with what that statement would mean. Anyway, if it's a new question, it should probably be posted separately as a new question..... $\endgroup$ – D.W. Sep 24 '13 at 7:18
  • $\begingroup$ thank you all , your posts help me a lot ... I found what I want in old complexity book called "computational complexity" by Chirstos H.Papadimitrious ... and state in one of the problem that PP is closed under reduction .... $\endgroup$ – Fayez Abdlrazaq Deab Sep 24 '13 at 10:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.