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 等数据库收录! |
|