Enumeration in Incremental FPT-Time

Publikation: Arbeitspapier/PreprintTechnical ReportForschung

Autoren

Forschungs-netzwerk anzeigen

Details

OriginalspracheEnglisch
PublikationsstatusElektronisch veröffentlicht (E-Pub) - 20 Apr. 2018

Abstract

In this paper, we study the relationship of parametrised 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 parametrised function classes and, in particular, introduce the parametrised 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 TF(para-NP) collapsing to F(FPT) is equivalent to OutputFPT coinciding with IncFPT. This result is in turn connected to a collapse in the classical function setting and eventually to the collapse of IncP and OutputP which proves the first direct connection of classical to parametrised enumeration.

Zitieren

Enumeration in Incremental FPT-Time. / Meier, Arne.
2018.

Publikation: Arbeitspapier/PreprintTechnical ReportForschung

Meier A. Enumeration in Incremental FPT-Time. 2018 Apr 20. Epub 2018 Apr 20.
Download
@techreport{1ef4181beeb148a2855eb2d017c1af4a,
title = "Enumeration in Incremental FPT-Time",
abstract = " In this paper, we study the relationship of parametrised 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 parametrised function classes and, in particular, introduce the parametrised 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 TF(para-NP) collapsing to F(FPT) is equivalent to OutputFPT coinciding with IncFPT. This result is in turn connected to a collapse in the classical function setting and eventually to the collapse of IncP and OutputP which proves the first direct connection of classical to parametrised enumeration. ",
keywords = "cs.LO, cs.CC",
author = "Arne Meier",
year = "2018",
month = apr,
day = "20",
language = "English",
type = "WorkingPaper",

}

Download

TY - UNPB

T1 - Enumeration in Incremental FPT-Time

AU - Meier, Arne

PY - 2018/4/20

Y1 - 2018/4/20

N2 - In this paper, we study the relationship of parametrised 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 parametrised function classes and, in particular, introduce the parametrised 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 TF(para-NP) collapsing to F(FPT) is equivalent to OutputFPT coinciding with IncFPT. This result is in turn connected to a collapse in the classical function setting and eventually to the collapse of IncP and OutputP which proves the first direct connection of classical to parametrised enumeration.

AB - In this paper, we study the relationship of parametrised 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 parametrised function classes and, in particular, introduce the parametrised 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 TF(para-NP) collapsing to F(FPT) is equivalent to OutputFPT coinciding with IncFPT. This result is in turn connected to a collapse in the classical function setting and eventually to the collapse of IncP and OutputP which proves the first direct connection of classical to parametrised enumeration.

KW - cs.LO

KW - cs.CC

M3 - Technical report

BT - Enumeration in Incremental FPT-Time

ER -

Von denselben Autoren