Index sets and parametric reductions (Q5945566)

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.