Time-space tradeoffs for counting NP solutions modulo integers

DOI10.1007/s00037-008-0248-yzbMath1149.68034OpenAlexW2179532697WikidataQ56806890 ScholiaQ56806890MaRDI QIDQ937201

R. 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

lower boundsdiagonalizationsatisfiabilityreversible computationmodular countingTime-space tradeoffs

Mathematics Subject Classification ID

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

Related Items (5)

An Improved Time-Space Lower Bound for Tautologies ⋮ Limits on alternation trading proofs for time-space lower bounds ⋮ Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle ⋮ Unnamed Item ⋮ Unifying known lower bounds via geometric complexity theory

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