Probabilistically checkable proofs for the Existential Theory of the Reals
We prove a PCP theorem for the existential theory of the reals, showing that MAX-ETR-INV is $\exists\mathbb{R}$-hard to approximate to within some constant factor. The existential theory of the reals (ETR) is a decision problem asking if there exists a set of real-valued variables satisfying some...
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Artículo |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2605.23517 http://arxiv.org/abs/2605.23517 |
| Etiquetas: |
Sin Etiquetas, Sea el primero en etiquetar este registro!
|