What people are saying - Write a review
We haven't found any reviews in the usual places.
Intractability of ReadOnce Resolution
Semantics versus Syntax versus Computations
25 other sections not shown
algorithm Ambos-Spies approximation approximation algorithm assume binary Boolean Boolean circuits circuit clauses closure property complete sets complexity classes Complexity Theory Computer Science concept constant construction contains Corollary corresponding defined Definition degree denote dense deterministic diagonalizations DSPACE(n elements enumerate ESPACE exists exponential extended fan-in finite formula func function f gates graph Hence hierarchy IEEE infinite input integer isomorphism Kolmogorov complexity language Lemma length logspace reductions lower bounds Lutz many-one nodes Note notion NP-complete one-way functions oracle oracle machine oracle Turing machine output pair player polynomial polynomial-time predicate Proc proof of Theorem Proposition prove PSPACE PSPACE-hard queries r.e. set random recursion theory reductions relativizable resource-bounded result satisfied Section self-reducible self-reducible sets sequence simulation sparse sets step strategy string Structure in Complexity subset tion tree truth assignment truth-table reducible Turing machine Turing reductions variables weight