
PreviousNext
A polynomial time computable function $h:\Sigma^*\to\Sigma^*$ whose range
is the set of tautologies in Propositional Logic (TAUT), is called
a proof system. Cook and Reckhow defined this concept
and in order to compare the relative strenth of different proof systems,
they considered the notion ...
more >>>
We define a general maximization operator max and a general minimization
operator min for complexity classes and study the inclusion structure of
the classes max.P, max.NP, max.coNP, min.P, min.NP, and min.coNP.
It turns out that Krentel's class OptP fits naturally into this frame-
work (it can be ...
more >>>
We survey recent results on the existence of polynomial time
approximation schemes for some dense instances of NP-hard
optimization problems. We indicate further some inherent limits
for existence of such schemes for some other dense instances of
the optimization problems.
PreviousNext