Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Adewale Sekoni:

TR18-018 | 22nd January 2018
John Hitchcock, Adewale Sekoni, Hadi Shafei

Polynomial-Time Random Oracles and Separating Complexity Classes

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 oracles. We consider two
notions of random oracles: p-random oracles in the sense of
martingales and resource-bounded measure (Lutz, 1992; Ambos-Spies ... more >>>

TR18-013 | 18th January 2018
John Hitchcock, Adewale Sekoni

Nondeterminisic Sublinear Time Has Measure 0 in P

The measure hypothesis is a quantitative strengthening of the P $\neq$ NP conjecture which asserts that NP is a nonnegligible subset of EXP. Cai, Sivakumar, and Strauss (1997) showed that the analogue of this hypothesis in P is false. In particular, they showed that NTIME[$n^{1/11}$] has measure 0 in P. ... more >>>

ISSN 1433-8092 | Imprint