Prior results show that most bounded query hierarchies cannot contain finite gaps. For example, it is known that P_(m+1)-tt^SAT = P_m-tt^SAT implies P_btt^SAT = P_m-tt^SAT and for all sets A

• FP_(m+1)-tt^A = FP_m-tt^A implies FP_btt^A = FP_m-tt^A
• P_(m+1)-T^A = P_m-T^A implies P_bT^A = ... more >>>

We study the average-case hardness of the class NP against deterministic polynomial time algorithms. We prove that there exists some constant $\mu > 0$ such that if there is some language in NP for which no deterministic polynomial time algorithm can decide L correctly on a $1- (log n)^{-\mu}$ fraction ... more >>>