Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with reversible computing:
TR07-036 | 6th April 2007
Ryan Williams

Time-Space Tradeoffs for Counting NP Solutions Modulo Integers

We prove the first time-space tradeoffs for counting the number of solutions to an NP problem modulo small integers, and also improve upon the known time-space tradeoffs for Sat. Let m be a positive integer, and define MODm-Sat to be the problem of determining if a given Boolean formula has ... more >>>

TR15-066 | 20th April 2015
Scott Aaronson, Daniel Grier, Luke Schaeffer

The Classification of Reversible Bit Operations

We present a complete classification of all possible sets of classical reversible gates acting on bits, in terms of which reversible transformations they generate, assuming swaps and ancilla bits are available for free. Our classification can be seen as the reversible-computing analogue of Post's lattice, a central result in mathematical ... more >>>

ISSN 1433-8092 | Imprint