16 citations · 25 across the 14 of their papers we have counts for
Showing 2010 · cs.CCShow all
2 papers · 2 filters
cs.CC2010
Collapsing and Separating Completeness Notions under Average-Case and Worst-Case Hypotheses
Xiaoyang Gu, John M. Hitchcock, A. Pavan
This paper presents the following results on sets that are complete for NP. 1. If there is a problem in NP that requires exponential time at almost all lengths, then every many-one…
cs.CC2010★ 5 cited
On the Power of Unambiguity in Logspace
Aduri Pavan, Raghunath Tewari, N. V. Vinodchandran
We report progress on the \NL vs \UL problem. [-] We show unconditionally that the complexity class $\ReachFewL\subseteq\UL$. This improves on the earlier known upper bound $\Reach…