Proving geometric algorithm non-solvability: An application of factoring polynomials

We explain how factoring polynomials modulo primes can be used in proving that for certain geometric optimisation problems there exists no exact algorithm under models of computation where the root of an algebraic equation is obtained using arithmetic operations and the extraction of kth roots. This leaves only numerical or symbolic approximations to the solution of these problems under these models. This letter describes work which is described in more detail in Bajaj (1984)—here we concentrate on the use of computer algebra, in particular factoring polynomials over the rationals using the MACSVMA system