Computers - Algorithms - Complexity
-
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.
-
Average-Case Complexity Forum
- Introduction and survey papers.
-
The P versus NP Problem
- Description of the P vs NP question, designated a Clay Mathematics Institute Millennium Prize Problems, by Stephen Cook.
-
A Compendium of NP Optimization Problems
- This is a preliminary version of the catalog of NP optimization problems.
-
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.
-
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, benchmarks, articles). A discussion forum is available as well.
-
SATLIB - The Satisfiability Library
- A collection of benchmark problems, solvers, and tools. One strong motivation for creating SATLIB is to provide a uniform test-bed for SAT solvers as well as a site for collecting SAT problem instances, algorithms, and empirical characterisations of the algorithms' performance.
-
Stas Busygin's NP-Completeness Page
- A proposal for solving NP-hard problems.
-
Computability and Complexity
- An online course on complexity.
-
Information-based Complexity
- People, publications, prizes.
-
Computational Complexity
- (Birkhäuser) Tables of contents from vol.7 (1998) on. Full text to subscribers via LINK.
-
Algorithms and Complexity
- A collection of bookmarks by Heribert Vollmer.
-
Hypertext Bibliography of Measures of Complexity
- Bruce Edmonds; Manchester Metropolitan University.
-
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 catalog of approximability results.
-
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.
-
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.
-
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, Canada; 26--27 June 2003.
-
Conferences of Interest for Complexity People
- Maintained at the Electronic Colloquium on Computational Complexity.
-
IEEE Conference on Computational Complexity
- This conference started as "Structure in Complexity Theory" in 1986. It recently acquired the new name "Conference on Computational Complexity", which was used for the first time in 1996. Committee membership, current announcements and archives.
