Learn more about Complexity Theory from our Theoretical directory

A Compendium of NP Optimization Problems - This is a preliminary version of the catalog of NP optimization problems.

Algorithms and Complexity - A collection of bookmarks by Heribert Vollmer.

Algorithms and Complexity - An overview of computational models and methods and how they relate to complexity

Algorithms and Complexity Research Area - The Oxford University Computing Laboratory's area on Algorithms and complexity

Challenging Benchmarks for SAT and CSP - Includes related links

Complexity of Algorithms - A list of topics from a Computer Science course involving complexity of algorithms. HTML and PS format.

Complexity Theory - Two set of lecture notes by Prof. Oded Goldreich

Computability and Complexity - An online course on complexity.

Computational Complexity and Programming Languages - Summaries of talks of the DIMACS workshop (July 1996)

Computational Complexity Theory - Wikipedia article.

Computational Complexity Theory - Definition of the subject

Constraint Satisfaction Problems - Research group in the Computing Laboratory

ECCC - Electronic Colloquium on Computational Complexity - A forum for the rapid and widespread interchange of ideas

Information-based Complexity - People

International Workshop on Implicit Computation Complexity - Webpages of past and forthcoming ICC conferences and related meetings. Next meeting as a satellite workshop of LICS'03: Ottawa

Lecture notes on Complexity - Collection of lecture notes by Prof. Eric Allender

P vs NP - Official version of the million dollar open problem in Theoretical Computer Science by the Clay Mathematical Institute.

Parameterized Complexity - Brief description

Probabilistically Checkable Proofs and Approximation - Pointers to some survey articles and their authors

Roberto Bayardo's Resources - Includes the relsat SAT solver and related papers.

SAT Live! - A collection of up-to-date links about the satisfiability problem (solvers

SATLIB - The Satisfiability Library - A collection of benchmark problems

Stas Busygin's NP-Completeness Page - A proposal for solving NP-hard problems.