The difference and truth-table hierarchies for NP
Köbler, Johannes ; Schöning, Uwe ; Wagner, Klaus W.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 21 (1987), p. 419-435 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU) 
@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},
     volume = {21},
     year = {1987},
     pages = {419-435},
     mrnumber = {928769},
     zbl = {0642.03024},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1987__21_4_419_0}
}

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) pp. 419-435. http://gdmltest.u-ga.fr/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).