Some Relations between Approximation Problems and PCPs over the Real Numbers |
| |
Authors: | Klaus Meer |
| |
Affiliation: | (1) Department of Mathematics and Computer Science, Syddansk Universitet, Campusvej 55, 5230 Odense M, Denmark |
| |
Abstract: | In 10] it was recently shown that
that is the existence of transparent long proofs for
was established. The latter denotes the class of real number decision problems verifiable in polynomial time as introduced
by Blum et al. 6]. The present paper is devoted to the question what impact a potential full real number
theorem
would have on approximation issues in the BSS model of computation. We study two natural optimization problems in the BSS
model. The first, denoted by MAX-QPS, is related to polynomial systems; the other, MAX-q-CAP, deals with algebraic circuits.
Our main results combine the PCP framework over
with approximation issues for these two problems. We also give a negative approximation result for a variant of the MAX-QPS
problem. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|