## Topics in computational complexity |

### What people are saying - Write a review

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

### Contents

An Independence Method | 10 |

The Xcalculus | 39 |

The Directed Subgraph Homeomorphism Problem | 96 |

2 other sections not shown

### Common terms and phrases

argument At.e axioms bucket Church-Rosser theorem closest pair combinatorial combinatory logic complexity computable corresponding defined described encoding example expression FINDINT fixed subgraph homeomorphism fixed type formula function f function symbols hashing Hence independent of Peano induction hypothesis input graph integer interval leaf labeled limit ordinal logic mathematical n-reduces natural number functions node mapping node-disjoint normal form normalization theorem notation NP-complete NP-hard parameter path pattern graph Peano Arithmetic pebble points polymorphic programming languages polymorphic type structure polymorphic X-calculus polynomial time algorithm possible primitive recursive functions programming languages proof of Theorem Proposition provable quantifier-free Rabin's algorithm randomized algorithm recursive calls redex reduces reduction sequence represented rules of inference sort procedure subgraph homeomorphism problem substituted successor ordinal Suppose term of type termination property transformation tree true Turing machine type application type polymorphic type recursive functions type s+t type variables typed X-calculus typed X-expression untyped X-calculus vector witness function Xx.e