Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Prabhu Manyem:

TR12-009 | 28th November 2011
Prabhu Manyem, Julien Ugon

Computational Complexity, NP Completeness and Optimization Duality: A Survey

We survey research that studies the connection between the computational complexity
of optimization problems on the one hand, and the duality gap between the primal and
dual optimization problems on the other. To our knowledge, this is the first survey that
connects the two very important areas. We further look ... more >>>

TR06-082 | 18th June 2006
Prabhu Manyem

Polynomial-Time Maximisation Classes: Syntactic Hierarchy

In Descriptive Complexity, there is a vast amount of literature on
decision problems, and their classes such as \textbf{P, NP, L and NL}. ~
However, research on the descriptive complexity of optimisation problems
has been limited. In a previous paper [Man], we characterised
the optimisation versions of \textbf{P} via expressions ... more >>>

ISSN 1433-8092 | Imprint