All reports by Author Hadi Shafei:

__
TR18-018
| 22nd January 2018
__

John Hitchcock, Adewale Sekoni, Hadi Shafei#### Polynomial-Time Random Oracles and Separating Complexity Classes

__
TR18-011
| 18th January 2018
__

John Hitchcock, Hadi Shafei#### Nonuniform Reductions and NP-Completeness

__
TR16-012
| 21st January 2016
__

John Hitchcock, Hadi Shafei#### Autoreducibility of NP-Complete Sets

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

John 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 isomorphism conjecture for NP and completeness for larger complexity classes. We study the power of nonuniform reductions for NP-completeness, obtaining both separations and upper bounds for ... more >>>

John 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 following:

- For every $k \geq 2$, there is a $k$-T-complete set for NP that is $k$-T autoreducible, but is not $k$-tt autoreducible ... more >>>