2012 | OriginalPaper | Chapter
Structural Complexity of Multiobjective NP Search Problems
Authors : Krzysztof Fleszar, Christian Glaßer, Fabian Lipp, Christian Reitwießner, Maximilian Witek
Published in: LATIN 2012: Theoretical Informatics
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.