Weak completeness in \(\text{E}\) and \(\text{E}_{2}\)

DOI10.1016/0304-3975(95)80016-6zbMath0873.68062OpenAlexW2094687533MaRDI QIDQ673644

Jack H. Lutz, David W. Juedes

Publication date: 28 February 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(95)80016-6

zbMATH Keywords

complexity classes

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (23)

NP-hard sets are superterse unless NP is small ⋮ Computability versus exact computability of martingales ⋮ Unnamed Item ⋮ Equivalence of measures of complexity classes ⋮ Unnamed Item ⋮ An excursion to the Kolmogorov random strings ⋮ Nonuniform reductions and NP-completeness ⋮ A note on measuring in P ⋮ The size of SPP ⋮ Nontriviality for exponential time w.r.t. weak reducibilities ⋮ Resource bounded randomness and weakly complete problems ⋮ Almost complete sets. ⋮ Upward separations and weaker hypotheses in resource-bounded measure ⋮ Algorithmic identification of probabilities is hard ⋮ Comparing nontriviality for E and EXP ⋮ Inseparability and strong hypotheses for disjoint NP pairs ⋮ A note on dimensions of polynomial size circuits ⋮ Equivalences between learning of data and probability distributions, and their applications ⋮ Strong Reductions and Isomorphism of Complete Sets ⋮ Polylog depth, highness and lowness for E ⋮ Resource bounded randomness and computational complexity ⋮ Weak completeness notions for exponential time ⋮ Recursive computational depth.

Cites Work

• Unnamed Item
• Almost everywhere high nonuniform complexity
• Weakly complete problems are not rare
• Process complexity and effective random tests
• Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie. (Randomness and probability. An algorithmic foundation of probability theory)
• Bi-immune sets for complexity classes
• The density and complexity of polynomial cores for intractable sets
• Some Observations about the Randomness of Hard Problems
• Instance complexity
• A Note on polynomial-size circuits with low resource-bounded Kolmogorov complexity
• Complete sets and closeness to complexity classes
• On the Computational Complexity of Algorithms
• [https://portal.mardi4nfdi.de/wiki/Publication:5587565 Klassifikation der Zufallsgesetze nach Komplexit�t und Ordnung]
• A unified approach to the definition of random sequences

This page was built for publication: Weak completeness in \(\text{E}\) and \(\text{E}_{2}\)