scientific article; zbMATH DE number 1775405

MaRDI QIDQ4542538zbMATH OpenFDO

Authors Richard Beigel, Harry Buhrman, Lance Fortnow

Publication date 1 August 2002

zbMATH Keywords

NEXPoracle

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On the unique satisfiability problem
• NP is as easy as detecting unique solutions
• Relativizing relativized computations
• scientific article; zbMATH DE number 866668
• scientific article; zbMATH DE number 4011940

Cited in

(15)

• NP is as easy as detecting unique solutions
• An oracle builder's toolkit
• Relativized worlds with an infinite hierarchy
• Two queries
• LWPP and WPP are not uniformly gap-definable
• Resource bounded symmetry of information revisited
• On the unique satisfiability problem
• The complexity of generating and checking proofs of membership
• Beyond \(\mathbf{P}^{\mathbf{NP}}=\mathbf{NEXP}\)
• scientific article; zbMATH DE number 866668 (Why is no real title available?)
• The complexity of symmetric Boolean parity Holant problems (extended abstract)
• Two oracles that force a big crunch
• A map of witness maps: new definitions and connections
• On the fine-grained complexity of parity problems
• Oracle separations for non-adaptive collapse-free quantum computing

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4542538)