10 papers
Exponential-Size Circuit Complexity is Comeager in Symmetric Exponential Time
John M. Hitchcock
Lutz (1987) introduced resource-bounded category and showed the circuit size class SIZE() is meager within ESPACE. Li (2024) established that the symmetric alternati…
Polynomial-Time Random Oracles and Separating Complexity Classes
John M. Hitchcock, Adewale Sekoni, Hadi Shafei
Bennett and Gill (1981) showed that P^A != NP^A != coNP^A for a random oracle A, with probability 1. We investigate whether this result extends to individual polynomial-time random…
Nondeterminisic Sublinear Time Has Measure 0 in P
John M. Hitchcock, Adewale Sekoni
The measure hypothesis is a quantitative strengthening of the P != NP conjecture which asserts that NP is a nonnegligible subset of EXP. Cai, Sivakumar, and Strauss (1997) showed t…
Nonuniform Reductions and NP-Completeness
John M. Hitchcock, Hadi Shafei
Nonuniformity is a central concept in computational complexity with powerful connections to circuit complexity and randomness. Nonuniform reductions have been used to study the iso…
Autoreducibility of NP-Complete Sets
John M. Hitchcock, Hadi Shafei
We study the polynomial-time autoreducibility of NP-complete sets and obtain separations under strong hypotheses for NP. Assuming there is a p-generic set in NP, we show the follow…
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…