16 citations · 45 across the 11 of their papers we have counts for
Showing 2011Show all
2 papers · 1 filter
math.LO2011★ 2 cited
Pseudo-jump inversion and SJT-hard sets
Rodney G. Downey, Noam Greenberg
There are noncomputable c.e.\ sets, computable from every SJT-hard c.e.\ set. This yields a natural pseudo-jump operator, increasing on all sets, which cannot be inverted back to a…
cs.CC2011
Confronting Intractability via Parameters
Rodney G. Downey, Dimitrios M. Thilikos
One approach to confronting computational hardness is to try to understand the contribution of various parameters to the running time of algorithms and the complexity of computatio…