If you want to make money online : Register now

Versions of NP with different logical unifiers

, , No Comments
Problem Detail: 

One formulation of NP is this: a language is in NP if it can be solved in polynomial time by an algorithm that has access to a special "Nondeterministic Bit" function, which branches the world into two alternate universes, writes a $1$ on the worktape in the first universe and a $0$ in the second, finishes the computation in each universe, and then returns the OR of the computation value of each universe.

If we replace the OR in this formulation with an AND, we get coNP.

I'm wondering what complexity class is described if we use the other nontrivial symmetric binary logical operators.

$\text{OR} \to NP$

$\text{AND} \to coNP$

$\text{XOR} \to \,?$

$\text{NAND} \to \, ?$

$\text{NOR} \to \,?$

$\text{EQUALS} \to \, ?$

Asked By : GMB
Answered By : Yuval Filmus

In the case of XOR or EQUALS, you get the class $\oplus$P, which includes the graph isomorphism problem.

In the case of NAND or NOR, I believe that you get PSPACE. Indeed, PSPACE is an upper bound, and you should be able to solve QBF in this model.

Best Answer from StackOverflow

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

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback