LINEAR-PROBLEMS AND LINEAR ALGORITHMS

Using predicate logic, the concept of a linear problem is formalized. The class of linear problems is huge, diverse, complex, and important. Linear and randomized linear algorithms are formalized. For each line ar problem, a linear algorithm is constructed that solves the problem and a randomized linear algorithm is constructed that completely solve s it, that is, for any data of the problem, the output set of the rand omized linear algorithm is identical to the solution set of the proble m. We obtain a single machine, referred to as the Universal (Randomize d) Linear Machine, which (completely) solves every instance of every l inear problem. Conversely, for each randomized linear algorithm, a lin ear problem is constructed that the algorithm completely solves. These constructions establish a one-to-one and onto correspondence from equ ivalence classes of linear problems to equivalence classes of randomiz ed linear algorithms. Our construction of (randomized) linear algorith ms to (completely) solve linear problems as well as the algorithms the mselves are based on Fourier Elimination and have superexponential com plexity. However, there is no evidence that the inefficiency of our me thods is unavoidable relative to the difficulty of the problem.