Polynomial-Time Random Oracles and Separating Complexity Classes.

John M. Hitchcock Adewale Sekoni Hadi Shafei

Published in: Electron. Colloquium Comput. Complex. (2018)

Keyphrases

worst case
computational complexity
tractable cases
special case
complexity measures
polynomial hierarchy
uniformly distributed
polynomial time complexity
complexity bounds
bounded treewidth
np hardness
computational cost
np hard
data sets
test cases
description logics
query complexity
machine learning