The following pages link to Average case completeness (Q1176231):
Displaying 32 items.
- A complete one-way function based on a finite rank free \(\mathbb{Z}\times\mathbb{Z}\)-module (Q376132) (← links)
- An approach to estimating the average-case complexity of postoptimality analysis of discrete optimization problems (Q464980) (← links)
- Average-case intractability vs. worst-case intractability (Q598182) (← links)
- Reducibility classes of P-selective sets (Q672155) (← links)
- A Random NP-complete problem for inversion of 2D cellular automata (Q672376) (← links)
- On complete one-way functions (Q734307) (← links)
- Generic case completeness (Q736607) (← links)
- Relations between average-case and worst-case complexity (Q927398) (← links)
- The computational complexity of pattern formation (Q1279214) (← links)
- On the complexity of deadlock detection in families of planar nets (Q1285587) (← links)
- On average time hierarchies (Q1313704) (← links)
- Some properties of sets tractable under every polynomial-time computable distribution (Q1350351) (← links)
- An average complexity measure that yields tight hierarchies (Q1355380) (← links)
- No NP problems averaging over ranking of distributions are harder (Q1391309) (← links)
- Generic-case complexity, decision problems in group theory, and random walks. (Q1399190) (← links)
- Complete distributional problems, hard languages, and resource-bounded measure (Q1575682) (← links)
- Polynomial time samplable distributions (Q1578504) (← links)
- From logic to tiling (Q1603696) (← links)
- Malign distributions for average case circuit complexity. (Q1854270) (← links)
- Complete on average Boolean satisfiability (Q1872642) (← links)
- Tilings: recursivity and regularity (Q1884987) (← links)
- On the average-case complexity of parameterized clique (Q2344729) (← links)
- Honest iteration schemes of randomizing algorithms (Q2365812) (← links)
- THE GENERIC DEGREES OF DENSITY-1 SETS, AND A CHARACTERIZATION OF THE HYPERARITHMETIC REALS (Q2795919) (← links)
- Asymptotic Density and the Theory of Computability: A Partial Survey (Q2970976) (← links)
- Asymptotic density, immunity and randomness (Q3195648) (← links)
- The complexity of generating test instances (Q5048939) (← links)
- Average-Case Completeness in Tag Systems (Q5090467) (← links)
- Nonexistence of minimal pairs for generic computability (Q5300075) (← links)
- Sets computable in polynomial time on average (Q6085734) (← links)
- Rankable distributions do not provide harder instances than uniform distributions (Q6085735) (← links)
- Structure in average case complexity (Q6487946) (← links)
