Content deleted Content added
No edit summary |
No edit summary |
||
Line 4:
The literature of average case complexity includes the following work:
* Shai Ben-David, Benny Chor, [[Oded Goldreich]], and [[Michael Luby]]. On the theory of average case complexity. In Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, pages 204–216. ACM, 1989.
* B. Selman D. Mitchell and H. Levesque. Hard and easy distributions of SAT problems. In Proceedings of the 10th National Conference on Artificial Intelligence, pages 459–465, 1992.
* John Franco. On the probabilistic performance of algorithms for the satisfiability problem. Information Processing Letters, 3:103–106, 1986.
| |||