Now showing items 1-1 of 1

    • A Quantum Time-Space Lower Bound for the Counting Hierarchy 

      Melkebeek, Dieter van; Watson, Thomas (University of Wisconsin-Madison Department of Computer Sciences, 2007)
      We obtain the first nontrivial time-space lower bound for quantum algorithms solving problems related to satisfiability. Our bound applies to MajSAT and MajMajSAT, which are complete problems for the first and second levels ...