4 papers · 1 filter
Random Permutations in Computational Complexity
John M. Hitchcock, Adewale Sekoni, Hadi Shafei
Classical results of Bennett and Gill (1981) show that with probability 1, relative to a random oracle , and with probability 1, relati…
Counting Martingales for Measure and Dimension in Complexity Classes
John M. Hitchcock, Adewale Sekoni, Hadi Shafei
This paper makes two primary contributions. First, we introduce the concept of counting martingales and use it to define counting measures, counting dimensions, and counting strong…
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…