[prev] [prev-tail] [tail] [up]

 Bibliographic Notes

The intensive interest in time and space complexity was spurted by Hartmanis and Stearns (1965). The relationship between RAM's and Turing transducers was considered in Cook and Reckhov (1973). The time hierarchy result in Theorem 5.2.1 and the Linear Speed-Up Theorem in Exercise 5.2.5 are from Hartmanis and Stearns (1965). Exercise 5.1.5 and Exercise 5.2.6 are from Stearns , Hartmanis , and Lewis (1965).

The polynomial time complexity of several problems was noticed by Cobham (1964). Edmonds (1965a) identified tractability with polynomial time, and informally defined the class NP. In addition, Edmonds (1965b) conjectured that the traveling-salesperson problem is in NP - P. Karp (1972) showed that the problem is NP-complete.

Cook (1971) laid the foundations for the theory of NP-completeness, by formally treating the P = NP question and exhibiting the existence of NP-complete problems. The importance of the theory was demonstrated by Karp (1972) by exhibiting the NP-completeness of a large number of classical problems. Similar investigation was carried out independently by Levin (1973).

The NP-completeness of the satisfiability problem was shown in Cook (1971). Karp (1972) showed the NP-completeness of the clique problem, the partition problem, and the 0 - 1 knapsack problem. The NP-completeness of the integer knapsack problem was shown by Lueker (1975). The NP-completeness of the inequivalence problem for LOOP(1) programs was shown by Hunt , Constable , and Sahni (1980).

The quadratic relationship between deterministic and nondeterministic space in Theorem 5.5.2 is due to Savitch (1970). The PSPACE-completeness of the membership problem for linear bounded automata in Theorem 5.5.3 is due to Karp (1972). The PSPACE-completeness of the inequivalence problem for finite-state automata in Theorem 5.5.4 is implied from Kleene (1956). The PSPACE-completeness of the emptiness problem for two-way deterministic finite-state automata in Exercise 5.5.4 is due to Hunt (1973). The closure in Theorem 5.5.5 of NSPACE (S(n)) under complementation was independently obtained by Immerman (1987) and Szelepcsenyi (1987). Theorem 5.5.6 is due to Sipser (1978). Exercise 5.5.5 is due to Hopcroft and Ullman (1969).

The P-completeness in Theorem 5.6.1 of the emptiness problem for context-free grammars is due to Jones and Laaser (1976). The P-completeness in Exercise 5.6.3 of CVP is due to Ladner (1975).

Additional insight into the topic of resource-bounded computation is offered in Hopcroft and Ullman (1979), Garey and Johnson (1979), and Stockmeyer (1985).

[prev] [prev-tail] [front] [up]