The difference and truth-table hierarchies for NP

 Access to full text

 Full (PDF)

1. 1. A. BLASS and Y. GUREVICH, On the Unique Satisfiability Problem, Information and Control, Vol. 55, 1982, pp. 80-88. Zbl0543.03027MR727739
2. 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. Zbl0599.03041MR749702
3. 3. J. CAI and L. HEMACHANDRA, The Boolean Hierarchy: Hardware Over NP, Proc. of the Structure in Complexity Theory Conference, Berkeley 1986 (to appear). Zbl0611.68018MR854893
4. 4. H. GALPERIN and A. WIGDERSON, Succinct representation of graphs, Information and Control, Vol. 56, 1986, pp. 183-198. Zbl0538.68053MR735503
5. 5. H. HELLER, Relativized Polynomial Hierarchies Extending Two Levels, Math. Syst. Theory, Vol. 17, 1984, pp. 71-84. Zbl0543.03028MR739981
6. 6. J. KÖBLER, Untersuchung verschiedener polynomieller Reduktionsklassen von NP, diploma thesis, University of Stuttgart, 1985. 
7. 7. R. E. LADNER, The Circuit Value Problem is log Space Complete for P, SIGACT News, Vol. 7, 1975, pp. 18-20. 
8. 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. Zbl0321.68039MR395319
9. 9. E. W. LEGETT and D. J. MOORE, Optimization Problems and the Polynomial Hierarchy, Theor. Comput. Sci., Vol 15, 1981, pp. 279-289. Zbl0459.68016MR632399
10. 10. C. H. PAPADIMITRIOU, On the Complexity of Unique Solutions, Proc. 23rd Symp. Found of Comput. Sci, 1982, pp. 14-20. MR780375
11. 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. Zbl0571.68028
12. 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. Zbl0475.03020MR598303
13. 13. L. J. STOCKMEYER, The Polynomial-Time Hierarchy, Theor. Comput. Sci., Vol. 3, 1977, pp. 1-22. Zbl0353.02024MR438810
14. 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). Zbl0581.68043
15. 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. Zbl0548.68039MR783486
16. 16. K. W. WAGNER, Maximum and Minimum Problems, and Some Closures of NP, Proc. 13th Intern Coll. Autom., Lang. and Progr., 1986 (to appear). 

1. Edith Hemaspaandra, Jörg Rothe, Holger Spakowski, Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP
2. J. Castro, C. Seara, Complexity classes between ${\Theta }_k^P$ and ${\Delta }_k^P$
3. Edith Hemaspaandra, Jörg Rothe, Holger Spakowski, Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP