Index sets and parametric reductions
type: Item
instance of: scholarly article
title: Index sets and parametric reductions
zbMATH Open document ID: 0989.03038
author: Rodney G. Downey
author: Michael R. Fellows
published in: Archive for Mathematical Logic
publication date: 2002-07-14T00:00:00Z
review text: Parameterized computational complexity theory has a few notions of polynomial reducibilities that take into account more carefully the extent to which different parameters that define a problem affect the complexity of the problem. The current paper investigates index sets associated with such reducibilities. It is shown that for a computable set \(A\), \(\{e:W_e \leq A \}\) is \(\Sigma^0_4\)-complete, where ``\(\leq\)'' is the ``basic'' parameterized polynomial reduction. It is also shown that \(\{e: W_e \text{ computable and } \equiv \emptyset \}\) is \(\Sigma^0_4\)-complete.
reviewed by: Marius Zimand
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 03D30
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 1657161
zbMATH Keywords: parameterized computational complexity
zbMATH Keywords: polynomial reducibilities
zbMATH Keywords: index sets
Wikidata QID: Q57360070
MaRDI profile type: MaRDI publication profile
full work available at URL: s001530100082
OpenAlex ID: W2024261644
DOI: 10.1007/S001530100082
description: scientific article; zbMATH DE number 1657161