6
$\begingroup$

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

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ If your "reduce" is a summation of the number of computations that accept, you get #P. $\endgroup$ – usul Feb 6 '15 at 16:47
  • $\begingroup$ Be careful about how you define the model. For one thing, it's critical that the program is never allowed to read the computation value ("return value") of any computation. $\endgroup$ – D.W.♦ Feb 7 '15 at 2:06
4
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ It might be helpful to elaborate how NAND leads to PSPACE or the ability to solve QBF. $\endgroup$ – D.W.♦ Feb 7 '15 at 2:08

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.