×

\(m\) solutions good, \(m-1\) solutions better. (English) Zbl 1144.68027

Summary: One of the main objectives of theoretical research in computational complexity and feasibility is to explain experimentally observed difference in complexity. Empirical evidence shows that the more solutions a system of equations has, the more difficult it is to solve it. Similarly, the more global maxima a continuous function has, the more difficult it is to locate them. Until now, these empirical facts have been only partially formalized: namely, it has been shown that problems with two or more solutions are more difficult to solve than problems with exactly one solution. In this paper, we extend this result and show that for every \(m\), problems with exactly \(m\) solutions are more difficult to solve than problems with \(m-1\) solutions. Rephrasing Orwell’s “Four legs good, two legs better”, we can describe this result as “\(m\) solutions good, \(m-1\) solutions better”.

MSC:

68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
90C60 Abstract computational complexity for mathematical programming problems
65G20 Algorithms with automatic result verification