Weakly complete problems are not rare
type: Item
instance of: scholarly article
title: Weakly complete problems are not rare
zbMATH Open document ID: 0849.03026
DOI: 10.1007/BF01206322
published in: Computational Complexity
publication date: 1996-11-04T00:00:00Z
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 03B25
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 908000
zbMATH Keywords: decision problems
zbMATH Keywords: exponential time
zbMATH Keywords: weakly complete problems
zbMATH Keywords: martingale diagonalization
author: David W. Juedes
MaRDI profile type: Publication
cites work: Q4525724
cites work: Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
cites work: The Complexity and Distribution of Hard Problems
cites work: An analysis of ML typability
cites work: Category and Measure in Complexity Classes
cites work: Almost everywhere high nonuniform complexity
cites work: Q4258588
cites work: Measure, Stochasticity, and the Density of Hard Languages
cites work: The definition of random sequences
cites work: Almost every set in exponential time is P-bi-immune
cites work: Klassifikation der Zufallsgesetze nach Komplexit�t und Ordnung
cites work: A unified approach to the definition of random sequences
cites work: Process complexity and effective random tests
cites work: Provably Difficult Combinatorial Games
cites work: Classifying the computational complexity of problems
Recommended article: Weakly Hard Problems
Recommended article: Some remarks on weak sufficiency
Recommended article: Completeness and weak completeness under polynomial-size circuits
Recommended article: On quantification of weak sequential completeness
Recommended article: Weak Completeness Notions for Exponential Time
Recommended article: Weak completeness notions for exponential time
Recommended article: Weak completeness in \(\text{E}\) and \(\text{E}_{2}\)
Recommended article: Q6156535
description: scientific article; zbMATH DE number 908000