Average case completeness
From MaRDI portal
Publication:1176231
DOI10.1016/0022-0000(91)90007-RzbMath0825.68420OpenAlexW2107993699WikidataQ56095059 ScholiaQ56095059MaRDI QIDQ1176231
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
Related Items
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, 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
