What people are saying - Write a review
We haven't found any reviews in the usual places.
Background and Definitions
Classes of Reductions and Relations On Sets
Equivalences and Isomorphisms
2 other sections not shown
0PEN QUESTI0N accept algorithm assume Automata Theory chapter class exponential class of feasible class of functions class of sets CNF-SAT complete sets complete with respect complexity class computable in p-time computable predicate conjunctive normal form consider context-sensitive languages Decision Problems decoding function define Definition deterministic time class DI0PH easy subsets encoding equivalent EXPTIME feasible computations Hartmanis implies integer inv(f known NP-complete sets L0GTIME length increasing reductions Let f lower bounds maps mathematics MQ#w multi-tape TM notion NPnco-NP one-one oracle P-1 complete p-reducible p-time computable functions p-time function P^NP P=NP question padding function partial order polynomial time isomorphic Polynomial Time Reducibility power of non-determinism Proc Project MAC question of invertibility recognized recursion theory recursive sets restriction sanforized satisfies Lemma 3.3 sets are p-isomorphic sets complete single-valuedness property study the structure Symposium on Theory Theorem 3.1 Theory of Computing TM's Turing Machines weakly computable