## Proceedings, Volume 9, Part 1994Springer-Verlag, 1994 - Computational complexity |

### From inside the book

Results 1-3 of 84

Page 94

Proof: The theorem is obtained by representing every gu as a convex

combination of some 7rao<;u, where Kn is the threshold function: ica(0) = 1 iff 0 >

a, ira(0) = 0 iff 0 < cv. This is possible for every function g. ir„ogu are

functions.

Proof: The theorem is obtained by representing every gu as a convex

combination of some 7rao<;u, where Kn is the threshold function: ica(0) = 1 iff 0 >

a, ira(0) = 0 iff 0 < cv. This is possible for every function g. ir„ogu are

**deterministic**functions.

Page 95

The proof for the

that T can be represented as a

for the uniform distribution. Proof of the observation (sketch): first assume that ...

The proof for the

**deterministic**case follows from theorem 16, by the observationthat T can be represented as a

**deterministic**convex combination, which is faithfulfor the uniform distribution. Proof of the observation (sketch): first assume that ...

Page 98

A non-

){-<xi, □ □ □ , -ix0}U {yi,---,yp} U {~,Vi>'-->~,yl8}- A non-

computes a function / G Ba as follows: For x G {0, 1}°, f(x) = 1 iff there exists a

setting ...

A non-

**deterministic**circuit is a circuit whose sources are labeled by {x\, • • • , xa}L){-<xi, □ □ □ , -ix0}U {yi,---,yp} U {~,Vi>'-->~,yl8}- A non-

**deterministic**circuitcomputes a function / G Ba as follows: For x G {0, 1}°, f(x) = 1 iff there exists a

setting ...

### What people are saying - Write a review

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

### Contents

Approximate Sets | 11 |

Polynomial Time TruthTable Reductions to PSelective Sets | 24 |

On the Query Complexity of Clique Size and Maximum Satisfiability | 31 |

Copyright | |

25 other sections not shown

### Other editions - View all

### Common terms and phrases

acceptance types algorithm assume binary Boolean Boolean circuit circuit collapses complete sets complexity classes Complexity Theory Computer Science configuration conjecture consider construction Corollary countable defined Definition denote deterministic DLOGTIME encoding exists exponential fan-in finite formula func function gate given graph guess hard hierarchy holds IEEE implies input head integer isomorphism leaf languages Lemma length live blocks logspace logspace reductions lower bound many-one many-one reduction martingale MAX3SAT NEXPTIME nodes nondeterministic Note NP-complete NP-hard O(logn optimal oracle oracle Turing machine output p-selective set P/poly path Player polynomial polynomial hierarchy polynomial-time predicate prob probabilistic Probabilistic Turing Machine probability Proc proof of Theorem proof systems Proposition protocol prove PSPACE PSPACE-hard recursive reductions representation class satisfying sequence simulate space bound strategy strings Structure in Complexity subset tape tion truth-table reducible Turing machine Ultrafilter unambiguous variables verifier weakly