Semidefinite programming and arithmetic circuit evaluation

Details Semidefinite programming and arithmetic circuit evaluation Semidefinite programming and arithmetic circuit evaluation

2005-12-09

arxiv.org/abs/cs/0512035v1

Computer Science

Computational Complexity

Submitted to Special issue of DAM in memory of L.Khachiyan

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Semidefinite programming and arithmetic circuit evaluation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Semidefinite programming and arithmetic circuit evaluation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Semidefinite programming and arithmetic circuit evaluation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-371135