×

zbMATH — the first resource for mathematics

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

MSC:
68Q45 Formal languages and automata
68Q25 Analysis of algorithms and problem complexity
68Q05 Models of computation (Turing machines, etc.) (MSC2010)