Quelques aspects du problème P = N P

Jacques Stern

Publications du Département de mathématiques (Lyon) (1982)

  • Volume: 1/B, Issue: 1B, page 15-26
  • ISSN: 0076-1656

How to cite

top

Stern, Jacques. "Quelques aspects du problème $P=NP$." Publications du Département de mathématiques (Lyon) 1/B.1B (1982): 15-26. <http://eudml.org/doc/274276>.

@article{Stern1982,
author = {Stern, Jacques},
journal = {Publications du Département de mathématiques (Lyon)},
keywords = {P problem; relativized problem, Meyer-Stockmeyer hierarchy; NP-complete},
language = {fre},
number = {1B},
pages = {15-26},
publisher = {Université Claude Bernard - Lyon 1},
title = {Quelques aspects du problème $P=NP$},
url = {http://eudml.org/doc/274276},
volume = {1/B},
year = {1982},
}

TY - JOUR
AU - Stern, Jacques
TI - Quelques aspects du problème $P=NP$
JO - Publications du Département de mathématiques (Lyon)
PY - 1982
PB - Université Claude Bernard - Lyon 1
VL - 1/B
IS - 1B
SP - 15
EP - 26
LA - fre
KW - P problem; relativized problem, Meyer-Stockmeyer hierarchy; NP-complete
UR - http://eudml.org/doc/274276
ER -

References

top
  1. [1] A.V. Aho, J.E. Hopcroft, J.D. Ullman, The design and analysis of computer algorithms, Addison-Wesley, Reading (1974). Zbl0326.68005MR413592
  2. [2] T.P. Baker, J. Gill, R.M. Solovay, Relativizations of the P = ? N P question, SIAM J. Comput4, (1975) 431-442. Zbl0323.68033MR395311
  3. [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. Zbl0397.03023MR451849
  4. [4] M.R. Garey, D.S. Johnson, Computers and intractability. A guide to the theory of NP-completeness, W.H. Freeman, San Francisco (1979). Zbl0411.68039MR519066
  5. [5] J.E. Hopcroft, J.D. Ullman, Introduction to automata theory, languages and computation, Addison-Wesley, Reading (1979). Zbl0980.68066MR645539
  6. [6] M. Santha, résultats non publiés. 
  7. [7] J. Stern, Séminaire : Algorithmes et complexité, Université de CAEN (1982) 
  8. [8] L.J. Stockmeyer, The polynomial time hierarchy, Theor. Comput. Sci.3 (1976) 1-22. Zbl0353.02024MR438810

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.