Hierarchies of Inefficient Kernelizability

Details Hierarchies of Inefficient Kernelizability Hierarchies of Inefficient Kernelizability

2011-10-05

arxiv.org/abs/1110.0976v1

Computer Science

Computational Complexity

Scientific paper

The framework of Bodlaender et al. (ICALP 2008) and Fortnow and Santhanam (STOC 2008) allows us to exclude the existence of polynomial kernels for a range of problems under reasonable complexity-theoretical assumptions. However, there are also some issues that are not addressed by this framework, including the existence of Turing kernels such as the "kernelization" of Leaf Out Branching(k) into a disjunction over n instances of size poly(k). Observing that Turing kernels are preserved by polynomial parametric transformations, we define a kernelization hardness hierarchy, akin to the M- and W-hierarchy of ordinary parameterized complexity, by the PPT-closure of problems that seem likely to be fundamentally hard for efficient Turing kernelization. We find that several previously considered problems are complete for our fundamental hardness class, including Min Ones d-SAT(k), Binary NDTM Halting(k), Connected Vertex Cover(k), and Clique(k log n), the clique problem parameterized by k log n.

Affiliated with

Also associated with

No associations

Rating

Hierarchies of Inefficient Kernelizability does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Hierarchies of Inefficient Kernelizability, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hierarchies of Inefficient Kernelizability will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-325223