Towards an Approximation Theory of Discrete Problems. Part I

Abstract

The purpose of this paper is to make the first step towards an approximation theory of discrete problems in which one can express and prove properties of approximating algorithms as well as carry out an approximate reasoning. We introduce an approximation propositional dynamic logic (APDL) with approximations of programs and formulas. We discuss the expressibility of APDL. The main theorem is the completeness theorem for a fragment of APDL. We consider also the approximation problem of properties expressible in APDL by a distinguished set of so called simple approximate formulas and programs, generated only from approximations of atomic properties and approximations of atomic programs. The solution of the uniform approximation problem is presented and a result about an appoximation of decision algorithms is given.