|
|
| Complexity |
|
| Listing: |
- 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, with links
to selected papers.
- Algorithms
and Complexity Research Area
The Oxford University Computing Laboratory's
area on Algorithms and complexity, with links
to lectures and information.
- 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.
- A
Compendium of NP Optimization Problems
This is a preliminary version of the catalog
of NP optimization problems.
- 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.
- Complexity
of Algorithms
A list of topics from a Computer Science course
involving complexity of algorithms. HTML and
PS format.
- Computability
and Complexity
An online course on complexity.
- 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.
- 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.
- Hypertext
Bibliography of Measures of Complexity
Bruce Edmonds; Manchester Metropolitan University.
- Information-based
Complexity
People, publications, prizes.
- The
P versus NP Problem
Description of the P vs NP question, designated
a Clay Mathematics Institute Millennium Prize
Problems, by Stephen Cook.
- 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.
- 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. Provides 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.
|
|
|
