QUANTUM NONDETERMINISTIC COMPUTATION BASED ON STATISTICS SUPERSELECTION RULES

Quantum states which obey certain symmetry superselection rules under identical particles permutation can be interpreted as computational st ates satisfying corresponding Boolean predicates. Given the NP-complet e problem of testing the satisfiability of a generic Boolean predicate P, we investigate the possibility of achieving quantum nondeterminist ic computation by deriving, from P, a physical situation in which the computational states satisfy P iff they satisfy a special fermion stat istics.