patternMinor
Versions of NP with different logical unifiers
Viewed 0 times
unifierswithdifferentversionslogical
Problem
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 \, ?$
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 \, ?$
Solution
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.
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.
Context
StackExchange Computer Science Q#38010, answer score: 4
Revisions (0)
No revisions yet.