Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR97-026 | 18th June 1997
Jochen Me\3ner, Jacobo Toran

Optimal proof systems for Propositional Logic and complete sets

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 >>>


TR97-025 | 26th May 1997
Harald Hempel, Gerd Wechsung

The Operators min and max on the Polynomial Hierarchy

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 >>>


TR97-024 | 9th June 1997
Marek Karpinski

Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems

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.

more >>>


previous PreviousNext next


ISSN 1433-8092 | Imprint