Berman, Piotr Relationship between density and deterministic complexity of NP-complete languages. (English) Zbl 0382.68068 Automata, languages and programming, 5th Colloq., Udine 1978, Lect. Notes Comput. Sci. 62, 63-71 (1978). Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page Cited in 2 ReviewsCited in 8 Documents MSC: 68Q45 Formal languages and automata 68Q25 Analysis of algorithms and problem complexity 68Q05 Models of computation (Turing machines, etc.) (MSC2010) PDFBibTeX XML