## Proceedings, Volume 9, Part 1994 |

### From inside the book

Results 1-3 of 30

Page 281

It is well known that RP 'CD {0, poly (n)) = PSPACE [17, 24]. In this paper, we

prove the following result. Theorem: RPCD(logn, 1) = PSPACE. This theorem

shows that a verifier that tosses O(logn) coins does not have to read the entire

debate between Arthur and Merlin. In fact, only a constant number of bits of the

debate are needed. We use this characterization of PSPACE to show that certain

stochastic

to compute ...

It is well known that RP 'CD {0, poly (n)) = PSPACE [17, 24]. In this paper, we

prove the following result. Theorem: RPCD(logn, 1) = PSPACE. This theorem

shows that a verifier that tosses O(logn) coins does not have to read the entire

debate between Arthur and Merlin. In fact, only a constant number of bits of the

debate are needed. We use this characterization of PSPACE to show that certain

stochastic

**PSPACE**-**hard**functions are as hard to approximate closely as they areto compute ...

Page 290

Theorem 3.5 There is a constant 0 < c < 1 such that approximating MAH-JONGG

within ratio c is

the nonapproximability results in the last section were based on the

characterization RPCD(logn, 1) = PSPACE. In this section, we present

nonapproximability results for different

characterization IP = PSPACE obtained in [17, 23]. The first problem we consider

here is also based on the ...

Theorem 3.5 There is a constant 0 < c < 1 such that approximating MAH-JONGG

within ratio c is

**PSPACE**-**hard**. 4 Nonapproximability using IP The proofs of all ofthe nonapproximability results in the last section were based on the

characterization RPCD(logn, 1) = PSPACE. In this section, we present

nonapproximability results for different

**PSPACE**-**hard**functions, based on thecharacterization IP = PSPACE obtained in [17, 23]. The first problem we consider

here is also based on the ...

Page 356

Abstract We use variants of the generalized CNF satisfiability problems SAT(S) of

[Sc78] to characterize the efficient approximability of a number of basic NP and

results in [CF+93, Ka93, Zu93], none of our proofs make use of interactive proof

systems or of probabilistically checkable debate systems. In particular assuming

P ^ NP- or P ^ PSPACE, we show that a number of the optimization problems

shown ...

Abstract We use variants of the generalized CNF satisfiability problems SAT(S) of

[Sc78] to characterize the efficient approximability of a number of basic NP and

**PSPACE**-**hard**optimization problems in the literature. In contrast with the recentresults in [CF+93, Ka93, Zu93], none of our proofs make use of interactive proof

systems or of probabilistically checkable debate systems. In particular assuming

P ^ NP- or P ^ PSPACE, we show that a number of the optimization problems

shown ...

### 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