Structural Complexity of Multiobjective NP Search Problems
LATIN 2012: Theoretical Informatics, volume 7256 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, (2012)DOI: 10.1007/978-3-642-29344-3_29
Abstract
An NP search problem is a multivalued function that maps instances to polynomially length-bounded solutions such that the validity of solutions is testable in polynomial time. NPMV_g denotes the class of these functions.
There are at least two computational tasks associated with an NP search problem:
(i) Find out whether a solution exists.
(ii) Compute an arbitrary solution.
Further computational tasks arise in settings with multiple objectives, for example:
(iii) Compute a solution that is minimal w.r.t. the first objective,
while the second objective does not exceed some budget.
Each such computational task defines a class of multivalued functions. We systematically investigate these classes and their relation to traditional complexity classes and classes of multivalued functions, like NP or max·P.
For multiobjective problems, some classes of computational tasks turn out to be equivalent to the function class NPMV_g , some to the class of decision problems NP, and some to a seemingly new class that includes both NPMV_g and NP. Under the assumption that certain exponential time classes are different, we show that there are computational tasks of multiobjective problems (more precisely functions in NPMV_g) that are Turing-inequivalent to any set.
Links and resources
Tags
community
@fabianlipp's tags highlighted