## Studies in complexity theory |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Complexity of Numerical Operations | 20 |

Structure of Real Numbers and Real Functions | 40 |

Future Directions | 51 |

Copyright | |

3 other sections not shown

### Common terms and phrases

algorithm approximate bounded quantifier Cauchy sequence Cg(n characterization co-NP complete sets complexity classes complexity of real computable functions computable real function computational complexity computational complexity theory Corollary CS(x defined Definition denote deterministic discrete complexity theory dyadic rational equivalent exists exponential EXPTIME f NP finite formula F function f Godel Hartmanis induction input isomorphic Journal on Computing Karp Mahaney many-one reducible McAloon models of arithmetic modulus function natural numbers nodes nomial non-standard model nondeterministic oracle TM p-isomorphic p-selective sets polynomial hierarchy polynomial size circuits polynomial time computable polynomial time hierarchy predicate primitive recursive functions probabilistic problems proof properties provably recursive function PSPACE PTAPE question r.e. sets real numbers recursive analysis recursive real function reducible to sparse regular initial segments relation representation self-reducibility sets in NP SIAM Journal sparse sets standard left cut strings structure subset techniques Theorem Theoretical Computer Science Turing machines Turing reducible unsatisfiable