Semidefinite programming and arithmetic circuit evaluation
<|reference_start|>Semidefinite programming and arithmetic circuit evaluation: 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.<|reference_end|>
@article{tarasov2005semidefinite,
    title={Semidefinite programming and arithmetic circuit evaluation},
    author={Sergey P. Tarasov, Mikhail N. Vyalyi},
    journal={arXiv preprint arXiv:cs/0512035},
    year={2005},
    archivePrefix={arXiv},
    eprint={cs/0512035},
    primaryClass={cs.CC}
}