2 papers
cs.CC2018
A theory of NP-completeness and ill-conditioning for approximate real computations
Gregorio Malajovich, Mike Shub
We develop a complexity theory for approximate real computations. We first produce a theory for exact computations but with condition numbers. The input size depends on a condition…
cs.CC2004
Computing Multi-Homogeneous Bezout Numbers is Hard
Gregorio Malajovich, Klaus Meer
The multi-homogeneous Bezout number is a bound for the number of solutions of a system of multi-homogeneous polynomial equations, in a suitable product of projective spaces. Given…