Quelques aspects du problème P=NP
Stern, Jacques
Publications du Département de mathématiques (Lyon), (1982), p. 15-26 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1982-01-01
@article{PDML_1982___1B_15_0,
     author = {Stern, Jacques},
     title = {Quelques aspects du probl\`eme $P=NP$},
     journal = {Publications du D\'epartement de math\'ematiques (Lyon)},
     year = {1982},
     pages = {15-26},
     mrnumber = {720724},
     zbl = {0534.68029},
     language = {fr},
     url = {http://dml.mathdoc.fr/item/PDML_1982___1B_15_0}
}

Stern, Jacques. Quelques aspects du problème $P=NP$. Publications du Département de mathématiques (Lyon),  (1982), pp. 15-26. http://gdmltest.u-ga.fr/item/PDML_1982___1B_15_0/

[1] A.V. Aho, J.E. Hopcroft, J.D. Ullman, The design and analysis of computer algorithms, Addison-Wesley, Reading (1974). | MR 413592 | Zbl 0326.68005

[2] T.P. Baker, J. Gill, R.M. Solovay, Relativizations of the P=?NP question, SIAM J. Comput 4, (1975) 431-442. | MR 395311 | Zbl 0323.68033

[3] T.P. Baker, A.L. Selman, A second step towards the polynomial hierarchy, Proc. 17 th Ann. Symp. on Foundations of Computer Science, IEEE Computer Society Long Beach (1976) 71-75. | MR 451849 | Zbl 0397.03023

[4] M.R. Garey, D.S. Johnson, Computers and intractability. A guide to the theory of NP-completeness, W.H. Freeman, San Francisco (1979). | MR 519066 | Zbl 0411.68039

[5] J.E. Hopcroft, J.D. Ullman, Introduction to automata theory, languages and computation, Addison-Wesley, Reading (1979). | MR 645539 | Zbl 0980.68066

[6] M. Santha, résultats non publiés.

[7] J. Stern, Séminaire : Algorithmes et complexité, Université de CAEN (1982)

[8] L.J. Stockmeyer, The polynomial time hierarchy, Theor. Comput. Sci. 3 (1976) 1-22. | MR 438810 | Zbl 0353.02024