If you want to make money online : Register now

# Versions of NP with different logical unifiers

, ,
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 \, ?$

###### 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.

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

3200 people like this