4 citations · 6 across the 3 of their papers we have counts for
Showing 2017Show all
2 papers · 1 filter
cs.CC2017
On W[1]-Hardness as Evidence for Intractability
Ralph C. Bottesch
The central conjecture of parameterized complexity states that FPT is not equal to W[1], and is generally regarded as the parameterized counterpart to P != NP. We revisit the issue…
cs.CC2017★ 1 cited
Relativization and Interactive Proof Systems in Parameterized Complexity Theory
Ralph Christian Bottesch
We introduce some classical complexity-theoretic techniques to Parameterized Complexity. First, we study relativization for the machine models that were used by Chen, Flum, and Gro…