A Framework for Studying the Complexity of General ε-Robust Problems

Abstract

We study a class of robust versions of ∃R-complete problems, parametrized by the robustness ε as part of the problem statement. By including ε in the problem statement and not the input, for some values of ε the problem can actually become easier than the original non-robust problem. Based on results for ε-Rudi, a robust version of unit disk intersection graph recognition, we derive a general framework for a wide family of ε-robust problems. The framework gives conditions on ε under which the ε-robust problem becomes polynomial-time solvable, or remains in ∃R, or admits a polynomially sized witness, or even becomes undecidable. Specifically, sufficient conditions on ε are given, independent of the specific problem, under which the ε-robust problem is in NP. In particular, ε should be polynomial-time computable and badly approximable by all real algebraic numbers. We begin with a detailed study of such badly approximable numbers, including a comparision with other results on approximation such as in diophantine approximation. We present an example of a computable, badly approximable number and conjecture that a polynomial-time computable, badly approximable number exists. We also present two example framework applications on robust versions of Packing and the Art Gallery Problem.