An Exact Correspondence of Linear Problems and Randomizing Linear Algorithms

• 成果类型: Article
• 署名作者: Eaves, B. Curtis; Rothblum, Uriel G.
• 署名单位: Stanford University; Technion Israel Institute of Technology
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2013.0629
• 发表日期: 2014
• 页码: 607-623
• 关键词: Complexity; Integers; FIELDS

摘要

A linear problem is completely solved by a randomizing linear algorithm if the set of data-solution pairs of the problem equals the set of input-output pairs of the algorithm over all randomizations. Linear problems are based on the predicate language over ordered fields. This class contains, for example, all linear programs, all bounded variable integer programs, all satisfiability problems in sentential logic, and models of conflict. Randomizing linear algorithms are based on a tree, arithmetic, comparisons, and random selections, over ordered fields, and with a restriction on certain operations. We show that the correspondence completely solved by is one-to-one and onto from equivalences of linear problems to equivalences of randomizing linear algorithms.