Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with P/poly:
TR98-026 | 5th May 1998
Richard Beigel

Gaps in Bounded Query Hierarchies

Prior results show that most bounded query hierarchies cannot
contain finite gaps. For example, it is known that
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>
and for all sets <i>A</i>
<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> 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 >>>

TR98-037 | 29th June 1998
Johannes Köbler, Rainer Schuler

Average-Case Intractability vs. Worst-Case Intractability

We use the assumption that all sets in NP (or other levels
of the polynomial-time hierarchy) have efficient average-case
algorithms to derive collapse consequences for MA, AM, and various
subclasses of P/poly. As a further consequence we show for
C in {P(PP), PSPACE} that ... more >>>

TR12-028 | 30th March 2012
Eric Allender, George Davie, Luke Friedman, Samuel Hopkins, Iddo Tzameret

Kolmogorov Complexity, Circuits, and the Strength of Formal Theories of Arithmetic

Revisions: 1

Can complexity classes be characterized in terms of efficient reducibility to the (undecidable) set of Kolmogorov-random strings? Although this might seem improbable, a series of papers has recently provided evidence that this may be the case. In particular, it is known that there is a class of problems $C$ defined ... more >>>

TR12-054 | 2nd May 2012
Eric Allender, Harry Buhrman, Luke Friedman, Bruno Loff

Reductions to the set of random strings:the resource-bounded case

Revisions: 1

This paper is motivated by a conjecture that BPP can be characterized in terms of polynomial-time nonadaptive reductions to the set of Kolmogorov-random strings. In this paper we show that an approach laid out by [Allender et al] to settle this conjecture cannot succeed without significant alteration, but that it ... more >>>

ISSN 1433-8092 | Imprint