Name
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. NPMVg 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 NPMVg, some to the class of decision problems NP, and some to a seemingly new class that includes both NPMVg 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 NPMVg) that are Turing-inequivalent to any set. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/978-3-642-29344-3_29 | LATIN |
Keywords | Field | DocType |
function class npmvg,certain exponential time class,multiobjective problem,structural complexity,np search problem,computational task,traditional complexity class,new class,arbitrary solution,multiobjective np search problem,decision problems np,multivalued function | Complexity class,Discrete mathematics,FP,Decision problem,Mathematical optimization,Combinatorics,Computer science,Complete,Search problem,Time complexity,Multivalued function,NP | Conference |
Volume | ISSN | Citations |
7256 | 0302-9743 | 0 |
PageRank | References | Authors |
0.34 | 15 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Krzysztof Fleszar | 1 | 368 | 25.38 |
| Christian Glaßer | 2 | 175 | 24.52 |
| Fabian Lipp | 3 | 14 | 4.44 |
| Christian Reitwießner | 4 | 39 | 4.81 |
| Maximilian Witek | 5 | 25 | 3.71 |