The difference and truth-table hierarchies for NP
Open Access
- 1 January 1987
- journal article
- Published by EDP Sciences in RAIRO - Theoretical Informatics and Applications
- Vol. 21 (4) , 419-435
- https://doi.org/10.1051/ita/1987210404191
Abstract
RAIRO - Theoretical Informatics and Applications, an international journal on theoretical computer science and its applicationsKeywords
This publication has 13 references indexed in Scilit:
- The boolean hierarchy: Hardware over NPPublished by Springer Nature ,1986
- Relativized polynomial hierarchies extending two levelsTheory of Computing Systems, 1984
- Quantitative Relativizations of Complexity ClassesSIAM Journal on Computing, 1984
- The complexity of problems concerning graphs with regularitiesPublished by Springer Nature ,1984
- Succinct representations of graphsInformation and Control, 1983
- On the complexity of unique solutionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1982
- On the unique satisfiability problemInformation and Control, 1982
- Optimization problems and the polynomial hierarchyTheoretical Computer Science, 1981
- A comparison of polynomial time reducibilitiesTheoretical Computer Science, 1975
- The circuit value problem is log space complete for PACM SIGACT News, 1975