What people are saying - Write a review
We haven't found any reviews in the usual places.
Building a DepartmentBuilding
A FirstOrder Approach to Graph
Effects of Internal Structure
3 other sections not shown
Other editions - View all
Complexity Theory Retrospective: In Honor of Juris Hartmanis on the Occasion ...
Alan L. Selman
No preview available - 2012
algorithm automata Berman-Hartmanis conjecture binary bits Boolean characterized co-NP collapse color class complete m-degree complete sets complexity classes compressed computational complexity computational complexity theory Computer Science construction context-free languages defined definition depth-first search deterministic equivalent example exist exponential finite first-order first-order logic follows Godel numberings graphs Hemachandra IEEE input tape Juris Hartmanis Kolmogorov complexity Kolmogorov random language Lemma length increasing linear lower bound m-complete m-reduction Mahaney Neil Immerman NEXP node noncollapsing nondeterministic NP-complete sets one-way functions optimal oracle machine output p-cheatable p-invertible p-isomorphic paddable padding functions paper Player polynomial hierarchy polynomial-time polynomial-time computable polynomially isomorphic Proc programming systems proof properties proved PSPACE queries question r.e. set random recursion theorem recursive functions reducible relativization self-reducibility Selman sets in NP simulation space sparse set string structural complexity theory Structure in Complexity Symp Theory of Computing tion tree Turing machine University vertex vertices Vitanyi