REPORTS > KEYWORD > P:
Richard Beigel
Gaps in Bounded Query Hierarchies
<html>
Prior results show that most bounded query hierarchies cannot
contain finite gaps. For example, it is known that
<center>
P<sub>(<i>m</i>+1)-tt</sub><sup>SAT</sup> = P<sub><i>m</i>-tt</sub><sup>SAT</sup> implies P<sub>btt</sub><sup>SAT</sup> = P<sub><i>m</i>-tt</sub><sup>SAT</sup>
</center>
and for all sets <i>A</i>
<ul>
<li> FP<sub>(<i>m</i>+1)-tt</sub><sup><i>A</i></sup> = FP<sub><i>m</i>-tt</sub><sup><i>A</i></sup> implies FP<sub>btt</sub><sup><i>A</i></sup> = FP<sub><i>m</i>-tt</sub><sup><i>A</i></sup>
</li>
<li> P<sub>(<i>m</i>+1)-T</sub><sup><i>A</i></sup> = P<sub><i>m</i>-T</sub><sup><i>A</i></sup> implies P<sub>bT</sub><sup><i>A</i></sup> = ...
more >>>
Denis Xavier Charles
A Note on Subgroup Membership Problem for PSL(2,p).
Comments: 1We show that there are infinitely many primes $p$, such
that the subgroup membership problem for PSL(2,p) belongs
to $\NP \cap \coNP$.
Parikshit Gopalan, Venkatesan Guruswami
Deterministic Hardness Amplification via Local GMD Decoding
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 >>>