Paper Info
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 a hierarchy of enumeration complexity classes for incremental fpt-time and relate it to the class DelayFPT. 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.
Year
Venue
Field
2018
arXiv: Logic in Computer Science
Complexity class,Discrete mathematics,Nondeterministic algorithm,Enumeration,Verifiable secret sharing,Hierarchy,Mathematics,TFNP
DocType
Volume
Citations 
Journal
abs/1804.07799
0
PageRank 
References 
Authors
0.34
0
1
Name
Order
Citations
PageRank
Arne Meier112619.00