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. |
Average-Case Complexity Forum
Introduction and survey papers. |
Blackbox - a SAT Technology Planning System
Blackbox is a planning system that works by converting problems specified in STRIPS notation into Boolean satisfiability problems, and then solving the problems with a variety of state-of-the-art satisfiability engines. |
Complexity and Approximation
Combinatorial optimization problems and their approximability properties: by G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi (Springer, 1999). Table of contents, errata, software supplement and a continuously updated |
Computational Complexity
(Birkhäuser) Tables of contents from vol.7 (1998) on. Full text to subscribers via LINK. |
Computational Complexity and Programming Languages
Summaries of talks of the DIMACS workshop (July 1996), collected by James Royer. |
Constraint Satisfaction Problems
Research group in the Computing Laboratory, Oxford University. |
Hypertext Bibliography of Measures of Complexity
Bruce Edmonds; Manchester Metropolitan University. |
Information-based Complexity
People, publications, prizes. |
Parameterized Complexity
Brief description, list of workers and problem compendium, compiled by Todd Wareham. |
Probabilistically Checkable Proofs and Approximation
Pointers to some survey articles and their authors, by M. Bellare. |
SAT Live!
A collection of up-to-date links about the satisfiability problem (solvers, benchmarks, articles). A discussion forum is available as well. |
The P versus NP Problem
Description of the P vs NP question, designated a Clay Mathematics Institute Millennium Prize Problems, by Stephen Cook. |
