Zobrazeno 1 - 10
of 331
pro vyhledávání: '"HITCHCOCK, JOHN"'
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
Externí odkaz:
http://arxiv.org/abs/1801.07317
Autor:
Hitchcock, John M., Shafei, Hadi
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 clas
Externí odkaz:
http://arxiv.org/abs/1801.05882
Autor:
Hitchcock, John M., Sekoni, Adewale
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 that the analogue of this hypothesis in P is false. In particular, they
Externí odkaz:
http://arxiv.org/abs/1801.05884
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Autor:
Hitchcock, John M., Shafei, Hadi
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
Externí odkaz:
http://arxiv.org/abs/1601.05494
Autor:
Leko, Melinda M.1 (AUTHOR) leko@coe.ufl.edu, Hitchcock, John H.2 (AUTHOR), Love, Hailey R.3 (AUTHOR), Houchins, David E.4 (AUTHOR), Conroy, Maureen A.1 (AUTHOR)
Publikováno v:
Exceptional Children. Jul2023, Vol. 89 Issue 4, p432-448. 17p.
Publikováno v:
Behavioral Disorders. May2023, Vol. 48 Issue 3, p212-223. 12p.
Publikováno v:
Behavioral Disorders. May2023, Vol. 48 Issue 3, p151-162. 12p.
This paper presents the following results on sets that are complete for NP. 1. If there is a problem in NP that requires exponential time at almost all lengths, then every many-one NP-complete set is complete under length-increasing reductions that a
Externí odkaz:
http://arxiv.org/abs/1001.0117