The difference and truth-table hierarchies for NP
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 21 (1987) no. 4, pp. 419-435.
@article{ITA_1987__21_4_419_0,
     author = {K\"obler, Johannes and Sch\"oning, Uwe and Wagner, Klaus W.},
     title = {The difference and truth-table hierarchies for {NP}},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {419--435},
     publisher = {EDP-Sciences},
     volume = {21},
     number = {4},
     year = {1987},
     zbl = {0642.03024},
     mrnumber = {928769},
     language = {en},
     url = {http://www.numdam.org/item/ITA_1987__21_4_419_0/}
}
TY  - JOUR
AU  - Köbler, Johannes
AU  - Schöning, Uwe
AU  - Wagner, Klaus W.
TI  - The difference and truth-table hierarchies for NP
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1987
DA  - 1987///
SP  - 419
EP  - 435
VL  - 21
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_1987__21_4_419_0/
UR  - https://zbmath.org/?q=an%3A0642.03024
UR  - https://www.ams.org/mathscinet-getitem?mr=928769
LA  - en
ID  - ITA_1987__21_4_419_0
ER  - 
Köbler, Johannes; Schöning, Uwe; Wagner, Klaus W. The difference and truth-table hierarchies for NP. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 21 (1987) no. 4, pp. 419-435. http://www.numdam.org/item/ITA_1987__21_4_419_0/

1. A. Blass and Y. Gurevich, On the Unique Satisfiability Problem, Information and Control, Vol. 55, 1982, pp. 80-88. | MR 727739 | Zbl 0543.03027

2. R. V. Book, T. J. Long and A. L. Selman, Quantitative Relativizations of Complexity Classes, S.I.A.M. J. Comput, Vol. 13, 1984, pp. 461-487. | MR 749702 | Zbl 0599.03041

3. J. Cai and L. Hemachandra, The Boolean Hierarchy: Hardware Over NP, Proc. of the Structure in Complexity Theory Conference, Berkeley 1986 (to appear). | MR 854893 | Zbl 0611.68018

4. H. Galperin and A. Wigderson, Succinct representation of graphs, Information and Control, Vol. 56, 1986, pp. 183-198. | MR 735503 | Zbl 0538.68053

5. H. Heller, Relativized Polynomial Hierarchies Extending Two Levels, Math. Syst. Theory, Vol. 17, 1984, pp. 71-84. | MR 739981 | Zbl 0543.03028

6. J. Köbler, Untersuchung verschiedener polynomieller Reduktionsklassen von NP, diploma thesis, University of Stuttgart, 1985.

7. R. E. Ladner, The Circuit Value Problem is log Space Complete for P, SIGACT News, Vol. 7, 1975, pp. 18-20.

8. R. E. Ladner, N. A. Lynch and A. L. Selman, A Comparison of Polynomial Time Reducibilities, Theor. Comput. Sci., Vol. 1, 1975, pp. 103-123. | MR 395319 | Zbl 0321.68039

9. E. W. Legett and D. J. Moore, Optimization Problems and the Polynomial Hierarchy, Theor. Comput. Sci., Vol 15, 1981, pp. 279-289. | MR 632399 | Zbl 0459.68016

10. C. H. Papadimitriou, On the Complexity of Unique Solutions, Proc. 23rd Symp. Found of Comput. Sci, 1982, pp. 14-20. | MR 780375

11. C. H. Papadimitriou and M. Yannakakis, The Complexity of Facets (and Some Facets of Complexity), Proc. 14th A.C.M. Symp. Theory of Comput., 1982, pp. 255-260.

12. D. B. Posner, Survey of Non-re Degress ≤0', in DRAKE/WAINER Eds, Recursion Theory: its Generalisations and Applications, Cambridge University Press, 1980, pp. 52-109. | MR 598303 | Zbl 0475.03020

13. L. J. Stockmeyer, The Polynomial-Time Hierarchy, Theor. Comput. Sci., Vol. 3, 1977, pp. 1-22. | MR 438810 | Zbl 0353.02024

14. G. Wechsung and K. W. Wagner, On the Boolean closure of NP, submitted for publication (extended abstract as: G. WECHSUNG, On the Boolean closure of NP; L.N.C.S., Vol. 199, 1985, pp. 485-493). | Zbl 0581.68043

15. K. W. Wagner, The Complexity of Problems Concerning Graphs with Regularities, Proc. Symp. Math. Found. of Comput. Sci., 1984, Lecture Notes in Computer Science, Vol. 176, 1984, pp. 544-552. | MR 783486 | Zbl 0548.68039

16. K. W. Wagner, Maximum and Minimum Problems, and Some Closures of NP, Proc. 13th Intern Coll. Autom., Lang. and Progr., 1986 (to appear).