Geodesic
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.

Voir la notice de l'article provenant de la source Numdam

@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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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, Tome 21 (1987) no. 4, pp. 419-435. http://geodesic.mathdoc.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. | Zbl | MR

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. | Zbl | MR

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

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

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

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. | Zbl | MR

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

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

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. | Zbl | MR

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

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

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. | Zbl | MR

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