2 papers
cs.CC2018
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…
cs.CC2018
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…