What people are saying - Write a review
We haven't found any reviews in the usual places.
26I W Savitch Relationships between Nondeterministic and Deterministic Tape Complexi
27l J Sciferas Relating Refined Complexity Classes J Comput Sys Sci 14 11977I
4 The trapdoor for the RSA system
Garey D Johnson and L Siockmeyer Some Simplified NPComplete Problems
accepts the input algorithm arbitrary assignment assume basic moves belongs Boolean expression class of problems co,NP computation sequence conjunctive normal form consider construct a Turing decide defined denotes deterministic Turing machine edge encoding encryption Eulerian path existential exists a Turing EXPTIME figure finite control forced,win game problem Godel number graph G halting problem Hamilton circuit problem Hamiltonian circuit Hamiltonian path problem head move hierarchy instantaneous description Kolmogorov complexity lemma length mathematics move function moves the head MPCP natural number NDTM node nondeterministic Turing machine NP,complete problem number theoretic oracle p,isomorphic p(ni path problem pebble game player prime elements prime number proposition proved PSPACE PSPACE,complete S(ni satisfiability problem scanning second tape Si(ni simulate solution solved space complexity T(ni tape head tape symbols terminates with yes Theorem time,bounded Turing machine travelling salesman problem undirected graph variables vertex cover vertices