Time-space tradeoffs for counting NP solutions modulo integers

DOI10.1007/S00037-008-0248-YMaRDI QIDQ937201zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Ryan Williams

Publication date 20 August 2008

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.92.1574

zbMATH Keywords

diagonalizationlower boundsmodular countingreversible computationsatisfiabilityTime-space tradeoffs

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Time-space tradeoffs for satisfiability
• Limits on alternation trading proofs for time-space lower bounds
• Time-space tradeoffs for SAT on nonuniform machines
• Complexity of generalized satisfiability counting problems
• scientific article; zbMATH DE number 2156275

Cited in

(6)

• Unifying known lower bounds via geometric complexity theory
• Time-space efficient simulations of quantum computations
• Limits on alternation trading proofs for time-space lower bounds
• Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle
• An Improved Time-Space Lower Bound for Tautologies
• Improved streaming algorithm for the Klee's measure problem and generalizations

This page was built for publication: Time-space tradeoffs for counting NP solutions modulo integers

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