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