Average case completeness

DOI10.1016/0022-0000(91)90007-RzbMath0825.68420OpenAlexW2107993699WikidataQ56095059 ScholiaQ56095059MaRDI QIDQ1176231

Yuri Gurevich

Publication date: 25 June 1992

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(91)90007-r

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (43)

Complete on average Boolean satisfiability ⋮ Honest iteration schemes of randomizing algorithms ⋮ Tilings: recursivity and regularity ⋮ The complexity of generating test instances ⋮ Recent results in hardness of approximation ⋮ Nonexistence of minimal pairs for generic computability ⋮ Some properties of sets tractable under every polynomial-time computable distribution ⋮ An average complexity measure that yields tight hierarchies ⋮ Generic complexity of the membership problem for semigroups of integer matrices ⋮ Asymptotic density, immunity and randomness ⋮ Average-case intractability vs. worst-case intractability ⋮ A complete one-way function based on a finite rank free \(\mathbb{Z}\times\mathbb{Z}\)-module ⋮ Secure commitment against a powerful adversary ⋮ No NP problems averaging over ranking of distributions are harder ⋮ Sets computable in polynomial time on average ⋮ Rankable distributions do not provide harder instances than uniform distributions ⋮ Complex tilings ⋮ Generic-case complexity, decision problems in group theory, and random walks. ⋮ Near-optimal dominating sets in dense random graphs in polynomial expected time ⋮ Reductions and convergence rates of average time ⋮ Asymptotic Density and the Theory of Computability: A Partial Survey ⋮ An approach to estimating the average-case complexity of postoptimality analysis of discrete optimization problems ⋮ Relations between average-case and worst-case complexity ⋮ ON GENERIC NP-COMPLETENESS OF THE BOOLEAN SATISFIABILITY PROBLEM ⋮ Reducibility classes of P-selective sets ⋮ A Random NP-complete problem for inversion of 2D cellular automata ⋮ ON GENERIC NP-COMPLETENESS OF THE PROBLEM OF BOOLEAN CIRCUITS SATISFIABILITY ⋮ ASYMPTOTIC DENSITY AND COMPUTABLY ENUMERABLE SETS ⋮ Structure in average case complexity ⋮ THE GENERIC DEGREES OF DENSITY-1 SETS, AND A CHARACTERIZATION OF THE HYPERARITHMETIC REALS ⋮ On complete one-way functions ⋮ Generic case completeness ⋮ An Average Case NP-complete Graph Colouring Problem ⋮ Average-Case Completeness in Tag Systems ⋮ The computational complexity of pattern formation ⋮ On the complexity of deadlock detection in families of planar nets ⋮ Complete distributional problems, hard languages, and resource-bounded measure ⋮ Polynomial time samplable distributions ⋮ Unnamed Item ⋮ Malign distributions for average case circuit complexity. ⋮ On the average-case complexity of parameterized clique ⋮ On average time hierarchies ⋮ From logic to tiling

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Average polynomial time complexity of some NP-complete problems
• Complexity results for classes of quantificational formulas
• On the definitions of some complexity classes of real numbers
• Some Examples of Combinatorial Averaging
• Average Case Complete Problems
• Expected Computation Time for Hamiltonian Path problem
• On the Computational Complexity of Program Scheme Equivalence
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• The NP-completeness column: An ongoing guide

This page was built for publication: Average case completeness