关键词：
linear programming
algebraic numbers
computational complexity
symbolic computation
ellipsoid method
polynomial-time algorithms
摘要：
We study the computational complexity of linear programs with coefficients that are real algebraic numbers under a Turing machine model of computation. After reviewing a method for exact representation of algebraic numbers under the Turing model, we show that the fundamental tasks of comparison and arithmetic can be performed in polynomial time. Our technique for establishing polynomial-time algorithms for comparison and arithmetic is distinct from the usual resultant-based approaches, and has the advantage that it provides a natural framework for analysis of the complexity of computational tasks, such as Gaussian elimination, that involve a sequence of arithmetic operations. Our main contribution is to show that a variant of the ellipsoid method can be used to solve linear programming in time polynomial in the encoding size of the problem coefficients and the degree of any algebraic extension that contains those coefficients.
欢迎来到三峡大学图书馆！
详细信息
中文科技期刊
