On truth-table reducibility to SAT
- 1 March 1991
- journal article
- Published by Elsevier in Information and Computation
- Vol. 91 (1) , 86-102
- https://doi.org/10.1016/0890-5401(91)90075-d
Abstract
No abstract availableKeywords
This publication has 10 references indexed in Scilit:
- The logarithmic alternation hierarchy collapses: AΣ2L = AΠ2LInformation and Computation, 1989
- The Boolean Hierarchy II: ApplicationsSIAM Journal on Computing, 1989
- The Boolean Hierarchy I: Structural PropertiesSIAM Journal on Computing, 1988
- The difference and truth-table hierarchies for NPRAIRO - Theoretical Informatics and Applications, 1987
- More complicated questions about maxima and minima, and some closures of NPTheoretical Computer Science, 1987
- The boolean hierarchy: Hardware over NPPublished by Springer Nature ,1986
- Log Space Recognition and Translation of Parenthesis LanguagesJournal of the ACM, 1977
- Relativization of questions about log space computabilityTheory of Computing Systems, 1976
- A comparison of polynomial time reducibilitiesTheoretical Computer Science, 1975
- The circuit value problem is log space complete for PACM SIGACT News, 1975