An Exact Correspondence of Linear Problems and Randomizing Linear Algorithms

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.

^†1947–2012.