## Combinatorics, computing and complexity |

### What people are saying - Write a review

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

### Contents

What is structural complexity theory? | 1 |

Constructing oracles by lower bound | 29 |

Randomness tally sets and complexity classes | 77 |

Copyright | |

6 other sections not shown

### Common terms and phrases

algorithm assignment bottom fanin collapsing combinatorial commutation monoids complexity classes complexity theory Computer Science consider construction defined definition denote DEXT diagonalization edge encoding exists an oracle finite free monoids free partially commutative gates graph Hastad hence hypergraphs IEEE induction input integer intractable inverse Kolmogorov complexity Latin square lower bound Math matroid nondeterministic Note NP-complete NP-hard NP(A one-to-one one-way functions optimal oracle machine oracle set pair parity circuit partially commutative group PH(A polymatroid polynomial hierarchy polynomial size circuits polynomial time computable polynomial time one-way polynomial-time hierarchy predicate preperfect probabilistic probability probability space Proc promise problem Proposition proved PSPACE PSPACE(A query r-system random oracle random restriction reducibility relativizations round Section space sparse set starter string structural complexity Structure in Complexity subset sufficiently large Switching Lemma tally set Theorem Theory of Computing Thue system tion Turing machine variables vy VLSI