Technical Report No. 26, November 1990 - Abstract

Edmund Ihler:
Approximation and Existential Second-Order Logic

The approximation properties of NP-complete optimization problems vary considerably. While for some problems, the solution cannot be approximated with constant accuracy unless P=NP, others can be approximated to any arbitrary degree of accuracy. In between there are problems for which approximation with some constant accuracy exists; for others, no constant accuracy approximation is known.

In this paper, we aim at capturing these kinds of approximation properties by introducing a natural hierarchy of logically defined classes of optimization problems. Our hierarchy makes use of the full expressive power of existential second-order logic; it contains the classes MAX SNP, MAX NP, and MAX Pi_1 as lowest classes