Publication:4359465
From MaRDI portal
zbMath0880.68046MaRDI QIDQ4359465
Publication date: 8 October 1997
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
The complexity of generating test instances, Average-Case Completeness in Tag Systems, Average-case complexity and decision problems in group theory., Guarantees for the success frequency of an algorithm for finding Dodgson-election winners, Generalized juntas and NP-hard sets, Relations between average-case and worst-case complexity, Frequency of correctness versus average polynomial time, Algorithms for the fixed point property, No NP problems averaging over ranking of distributions are harder, Generic-case complexity, decision problems in group theory, and random walks., Complete distributional problems, hard languages, and resource-bounded measure, Complete on average Boolean satisfiability, Computational depth: Concept and applications, Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey, An efficient local search method for random 3-satisfiability