Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > P:
Reports tagged with P:
TR98-026 | 5th May 1998
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 >>>

TR01-029 | 27th March 2001
Denis Xavier Charles

#### A Note on Subgroup Membership Problem for PSL(2,p).

We show that there are infinitely many primes $p$, such
that the subgroup membership problem for PSL(2,p) belongs
to $\NP \cap \coNP$.

more >>>

TR07-089 | 13th September 2007
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 >>>

TR13-188 | 13th December 2013
Christian Glaßer, Maximilian Witek

#### Autoreducibility and Mitoticity of Logspace-Complete Sets for NP and Other Classes

We study the autoreducibility and mitoticity of complete sets for NP and other complexity classes, where the main focus is on logspace reducibilities. In particular, we obtain:
- For NP and all other classes of the PH: each logspace many-one-complete set is logspace Turing-autoreducible.
- For P, the delta-levels of ... more >>>

TR17-001 | 6th January 2017
Stephen Cook, Bruce Kapron

#### A Survey of Classes of Primitive Recursive Functions

This paper is a transcription of mimeographed course notes titled A Survey of Classes of Primitive Recursive Functions", by S.A. Cook, for the University of California Berkeley course Math 290, Sect. 14, January 1967. The notes present a survey of subrecursive function
classes (and classes of relations based on these ... more >>>

ISSN 1433-8092 | Imprint