An Exact Correspondence of Linear Problems and Randomizing Linear Algorithms

作者：Eaves B Curtis^*; Rothblum Uriel G

来源：Mathematics of Operations Research, 2014, 39(3): 607-623.

DOI：10.1287/moor.2013.0629

• linear problems
• data-solution pairs
• randomizing linear algorithms
• input-output pairs
• equivalence
• bijection
• predicate language
• parametric Fourier quantifier elimination
• ordered 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.

• 出版日期2014-8