@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}, mrnumber = {928769}, zbl = {0642.03024}, 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 SP - 419 EP - 435 VL - 21 IS - 4 PB - EDP-Sciences UR - http://www.numdam.org/item/ITA_1987__21_4_419_0/ LA - en ID - ITA_1987__21_4_419_0 ER -
%0 Journal Article %A Köbler, Johannes %A Schöning, Uwe %A Wagner, Klaus W. %T The difference and truth-table hierarchies for NP %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 1987 %P 419-435 %V 21 %N 4 %I EDP-Sciences %U http://www.numdam.org/item/ITA_1987__21_4_419_0/ %G en %F 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, Volume 21 (1987) no. 4, pp. 419-435. http://www.numdam.org/item/ITA_1987__21_4_419_0/
1. On the Unique Satisfiability Problem, Information and Control, Vol. 55, 1982, pp. 80-88. | MR | Zbl
and ,2. Quantitative Relativizations of Complexity Classes, S.I.A.M. J. Comput, Vol. 13, 1984, pp. 461-487. | MR | Zbl
, and ,3. The Boolean Hierarchy: Hardware Over NP, Proc. of the Structure in Complexity Theory Conference, Berkeley 1986 (to appear). | MR | Zbl
and ,4. Succinct representation of graphs, Information and Control, Vol. 56, 1986, pp. 183-198. | MR | Zbl
and ,5. Relativized Polynomial Hierarchies Extending Two Levels, Math. Syst. Theory, Vol. 17, 1984, pp. 71-84. | MR | Zbl
,6. Untersuchung verschiedener polynomieller Reduktionsklassen von NP, diploma thesis, University of Stuttgart, 1985.
,7. The Circuit Value Problem is log Space Complete for P, SIGACT News, Vol. 7, 1975, pp. 18-20.
,8. A Comparison of Polynomial Time Reducibilities, Theor. Comput. Sci., Vol. 1, 1975, pp. 103-123. | MR | Zbl
, and ,9. Optimization Problems and the Polynomial Hierarchy, Theor. Comput. Sci., Vol 15, 1981, pp. 279-289. | MR | Zbl
and ,10. On the Complexity of Unique Solutions, Proc. 23rd Symp. Found of Comput. Sci, 1982, pp. 14-20. | MR
,11. The Complexity of Facets (and Some Facets of Complexity), Proc. 14th A.C.M. Symp. Theory of Comput., 1982, pp. 255-260.
and ,12. Survey of Non-re Degress ≤0', in DRAKE/WAINER Eds, Recursion Theory: its Generalisations and Applications, Cambridge University Press, 1980, pp. 52-109. | MR | Zbl
,13. The Polynomial-Time Hierarchy, Theor. Comput. Sci., Vol. 3, 1977, pp. 1-22. | MR | Zbl
,14. 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
and ,15. 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 | Zbl
,16. Maximum and Minimum Problems, and Some Closures of NP, Proc. 13th Intern Coll. Autom., Lang. and Progr., 1986 (to appear).
,