We consider the following questions: 1. Can one compute satisfying assignments for satisfiable Boolean formulas in polynomial time with parallel queries to NP? 2. Is the unique optimal clique problem (UOCLIQUE) complete for P~(NP[O(log n)]? 3. Is the unique satisfiability problem (USAT) NP hard?
展开▼
