Issues in NP-Optimization and Approximation

Optimization or finding the best solution for a problem amongst several possible ones is one of the central themes in computing. In particular, NP-optimization (NPO) problems, examples of which include such well-known problems like Integer Programming and Traveling Salesperson Problem, have proved to be of great practical and theoretical importance. Different NPO problems exhibit starkly different properties and understanding the structure of these problems and their classification has been a long- standing goal in theoretical computer science. This thesis investigates the properties of NPO problems in two settings. In the first part of the thesis we investigate how the logical expressibility of NPO problems relates to some of their computational properties like approximability and self-improvement. In the second part we study NPO problems in the context of a relativeloy new model called the counterexample model. This allows us to achieve two objectives: Firstly, it gives us a framework to study and analyze incremental computation of optimal or near-optimal solutions in an abstract setting. This is useful because, in practice, for most of the NPO problems, one has to resort to inexact algorithms which work incrementally towards computing a good solution. Secondly, it gives us a way to precisely formulate and study questions about the structure of these problems which we believe are fundamental from theoretical point of view - for example, how much does the knowledge of one solution of a problem help in computing another solution