Semidefinite programming and arithmetic circuit evaluation
| dc.creator | Tarasov, Sergey P. | |
| dc.creator | Vyalyi, Mikhail N. | |
| dc.date | 2005-12-09 | |
| dc.date.accessioned | 2026-07-07T06:53:48Z | |
| dc.date.available | 2026-07-07T06:53:48Z | |
| dc.description | A rational number can be naturally presented by an arithmetic computation (AC): a sequence of elementary arithmetic operations starting from a fixed constant, say 1. The asymptotic complexity issues of such a representation are studied e.g. in the framework of the algebraic complexity theory over arbitrary field. Here we study a related problem of the complexity of performing arithmetic operations and computing elementary predicates, e.g. ``='' or ``>'', on rational numbers given by AC. In the first place, we prove that AC can be efficiently simulated by the exact semidefinite programming (SDP). Secondly, we give a BPP-algorithm for the equality predicate. Thirdly, we put ``>''-predicate into the complexity class PSPACE. We conjecture that ``>''-predicate is hard to compute. This conjecture, if true, would clarify the complexity status of the exact SDP - a well known open problem in the field of mathematical programming. | |
| dc.description | Submitted to Special issue of DAM in memory of L.Khachiyan | |
| dc.identifier | https://arxiv.org/abs/cs/0512035 | |
| dc.identifier | http://arxiv.org/abs/cs/0512035 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/105720 | |
| dc.subject | Computational Complexity | |
| dc.subject | F.1.3 | |
| dc.title | Semidefinite programming and arithmetic circuit evaluation | |
| dc.type | text |