Introduction

In the following we refer to standard complexity classes (see [ 195 ]). We recall that a function t(n) is `quasi-polynomial' if a constant c exists such that and we denote by QP, QNP, and QR the analogues of the usual complexity classes in the quasi-polynomial time domain.

 
• NPO Problems: Definitions and Preliminaries
• Approximate Algorithms and Approximation Classes
• Completeness in Approximation Classes
• A list of NPO problems
• Improving the compendium