2005/12/09 by S. Yu. Tarasov, Tarasov, Sergey P., M. Vyalyi +1
Computer Science · Engineering · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #F.1.3 #FOS: Computer and information sciences #Low-power high-performance VLSI design #Numerical Methods and Algorithms
paper · pdf · doi:10.48550/arxiv.cs/0512035
openalex publication_date 2005/12/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.