5 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…
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…