|
|
1. |
A Compendium of NP Optimization Problems
-
This is a preliminary version of the catalog of NP optimization problems.
|
|
|
2. |
Algorithms and Complexity
-
An overview of computational models and methods and how they relate to complexity, with links to selected papers.
|
|
|
3. |
Algorithms and Complexity Research Area
-
The Oxford University Computing Laboratory's area on algorithms and complexity, with links to lectures and information.
|
|
|
4. |
Average-Case Complexity Forum
-
Introduction and survey papers.
|
|
|
5. |
Complexity of Algorithms
-
A list of topics from a Computer Science course involving complexity of algorithms. HTML and PS format.
|
|
|
6. |
Complexity Theory
-
Two set of lecture notes by Prof. Oded Goldreich, Weizmann Institute.
|
|
|
7. |
Computational Complexity and Programming Languages
-
Summaries of talks of the DIMACS workshop (July 1996), collected by James Royer.
|
|
|
8. |
Computational Complexity Theory
-
NodeWorks Encyclopedia article.
|
|
|
9. |
Information-based Complexity
-
People, publications, prizes.
|
|
|
10. |
Lecture notes on Complexity
-
Collection of lecture notes by Prof. Eric Allender, Rutgers University.
|
|
|
11. |
Parameterized Complexity
-
Brief description, list of workers and problem compendium, compiled by Todd Wareham.
|
|
|
12. |
Probabilistically Checkable Proofs and Approximation
-
Pointers to some survey articles and their authors, by M. Bellare.
|
|
|
13. |
SAT Live!
-
A collection of up-to-date links about the satisfiability problem (solvers, benchmarks, articles). A discussion forum is available as well.
|
|
|
14. |
Stas Busygin's NP-Completeness Page
-
A proposal for solving NP-hard problems.
|
|
|
15. |
Algorithms and Complexity
-
A collection of bookmarks by Heribert Vollmer.
|
|
|
16. |
Challenging Benchmarks for SAT and CSP
-
Includes related links, references and a summary of the results for the SAT benchmarks used in SAT Competition 2004.
|
|
|
17. |
Computability and Complexity
-
An online course on complexity.
|
|
|
18. |
Computational Complexity Theory
-
Definition of the subject, links.
|
|
|
19. |
Constraint Satisfaction Problems
-
Research group in the Computing Laboratory, Oxford University.
|
|
|
20. |
ECCC - Electronic Colloquium on Computational Complexity
-
A forum for the rapid and widespread interchange of ideas, techniques, and research in computational complexity. Research reports, surveys and books; meetings, discussions and web resources.
|
|
|
21. |
P vs NP
-
Official version of the million dollar open problem in Theoretical Computer Science by the Clay Mathematical Institute.
|
