M.Sc Thesis | |

M.Sc Student | Magid Yonit |
---|---|

Subject | BSS Model of Computation over the Reals and Choice Operator |

Department | Department of Computer Science |

Supervisor | PROFESSOR EMERITUS Johann Makowsky |

Full Thesis text |

B.C. Eaves and U.G. Rothblum studied the notion of linear algorithms and linear problems over the reals as an ordered field. They showed that by augmenting straight-line programs with random assignments from specified intervals one gets an exact correspondence between linear problems and algorithms. The class of the linear problems is huge, diverse, complex and important.

The class contains, for example, finding the rank of matrices, optimizing linear programming problems, optimizing bounded variable integer programs, solving linear complementary problems and determining satisfiability in sentential logic.

The notion of random assignments (i.e. arbitrarily picking a value to assign, no probability space involved) was introduced in order to achieve the complete solution set of a problem, which is useful in many cases.

The purpose of this research thesis is to place Eaves and Rothblum's result in a wider algorithmic context.

We extend this idea to
algebraic problems and algorithms by introducing random assignments for roots
of univariate polynomials. We also give an alternative proof of the
Eaves-Rothblum characterization of the linear case. In both cases we give
complexity estimates based on the complexity of cylindrical algebraic
decomposition or, in the linear case, of the simplex algorithm. We also discuss
the notion of *choice operators* as a more generalized form of random
assignments.