Incremental FPT Delay
In this paper, we study the relationship of parameterized enumeration complexity classes defined by Creignou et al. (MFCS 2013). Specifically, we introduce two hierarchies (IncFPTa and CapIncFPTa) of enumeration complexity classes for incremental fpt-time in terms of exponent slices and show how the...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2020-05-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/13/5/122 |
| _version_ | 1797567895678484480 |
|---|---|
| author | Arne Meier |
| author_facet | Arne Meier |
| author_sort | Arne Meier |
| collection | DOAJ |
| description | In this paper, we study the relationship of parameterized enumeration complexity classes defined by Creignou et al. (MFCS 2013). Specifically, we introduce two hierarchies (IncFPTa and CapIncFPTa) of enumeration complexity classes for incremental fpt-time in terms of exponent slices and show how they interleave. Furthermore, we define several parameterized function classes and, in particular, introduce the parameterized counterpart of the class of nondeterministic multivalued functions with values that are polynomially verifiable and guaranteed to exist, TFNP, known from Megiddo and Papadimitriou (TCS 1991). We show that this class TF(para-NP), the restriction of the function variant of NP to total functions, collapsing to F(FPT), the function variant of FPT, is equivalent to the result that OutputFPT coincides with IncFPT. In addition, these collapses are shown to be equivalent to TFNP = FP, and also equivalent to P equals NP intersected with coNP. Finally, we show that these two collapses are equivalent to the collapse of IncP and OutputP in the classical setting. These results are the first direct connections of collapses in parameterized enumeration complexity to collapses in classical enumeration complexity, parameterized function complexity, classical function complexity, and computational complexity theory. |
| first_indexed | 2024-03-10T19:48:43Z |
| format | Article |
| id | doaj.art-84b9110c814a490ba6ee47eef852b08f |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-03-10T19:48:43Z |
| publishDate | 2020-05-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-84b9110c814a490ba6ee47eef852b08f2023-11-20T00:36:35ZengMDPI AGAlgorithms1999-48932020-05-0113512210.3390/a13050122Incremental FPT DelayArne Meier0Institut für Theoretische Informatik, Leibniz Universität Hannover, 30167 Hannover, GermanyIn this paper, we study the relationship of parameterized enumeration complexity classes defined by Creignou et al. (MFCS 2013). Specifically, we introduce two hierarchies (IncFPTa and CapIncFPTa) of enumeration complexity classes for incremental fpt-time in terms of exponent slices and show how they interleave. Furthermore, we define several parameterized function classes and, in particular, introduce the parameterized counterpart of the class of nondeterministic multivalued functions with values that are polynomially verifiable and guaranteed to exist, TFNP, known from Megiddo and Papadimitriou (TCS 1991). We show that this class TF(para-NP), the restriction of the function variant of NP to total functions, collapsing to F(FPT), the function variant of FPT, is equivalent to the result that OutputFPT coincides with IncFPT. In addition, these collapses are shown to be equivalent to TFNP = FP, and also equivalent to P equals NP intersected with coNP. Finally, we show that these two collapses are equivalent to the collapse of IncP and OutputP in the classical setting. These results are the first direct connections of collapses in parameterized enumeration complexity to collapses in classical enumeration complexity, parameterized function complexity, classical function complexity, and computational complexity theory.https://www.mdpi.com/1999-4893/13/5/122parameterized complexityfunction complexityenumeration |
| spellingShingle | Arne Meier Incremental FPT Delay Algorithms parameterized complexity function complexity enumeration |
| title | Incremental FPT Delay |
| title_full | Incremental FPT Delay |
| title_fullStr | Incremental FPT Delay |
| title_full_unstemmed | Incremental FPT Delay |
| title_short | Incremental FPT Delay |
| title_sort | incremental fpt delay |
| topic | parameterized complexity function complexity enumeration |
| url | https://www.mdpi.com/1999-4893/13/5/122 |
| work_keys_str_mv | AT arnemeier incrementalfptdelay |