Computing Theory

• Theory of Computing

• Computing Complexity
• NP and NP-completeness
• The complexity of guarding an art gallery
• A Concise Tutorial on Finite Automata
• Stas Busygin's NP-Completeness Page
• comp.theory FAQ, frequently asked questions about CS theory.
• Learning Dynamical Systems: A Tutorial
• Notes on Finite Automata
• 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.
• A Compendium of NP Optimization Problems - This is a preliminary version of the catalog of NP optimization problems.
• Computability and Complexity - An online course on complexity.
• 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.
• 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.
• 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.

Other Links Related to Math and So on.

• Netlib, a collection of mathematical software, papers, and databases.
• Second DIMACS Challenge on clique, coloring, satisfiability.
• GAMS, a guide to available math software.
• Decision Tree for Optimization Software, a catalogue of optimization software.
• The Stony Brook Algorithm Repository, well-known algorithms and solvers.
• Computability and Complexity, an online course on complexity.
• INFORMS OR/MS Resources, former Mike Trick's OR page.
• A compendium of NP optimization problems, such problems known today.
• OR-Library, test instances of various optimization problems.
• SATLIB - The Satisfiability Library, a site for the satisfiability problem.
• SAT Live! Up-to-date links for the SATisfiability problem.
• TSPLIB, Travelling Salesman, Hamilton Cycle and other related instances.
• The Hamiltonian Page, Pablo Moscato's page for HCP.
• Hamiltonian Circuit Problem by Michiro Nasu, contains an HCP solver.
• Blackbox, a SAT technology planning system.
• Roberto Bayardo's Resources, an excellent SAT solver and related papers.
• Patterncraft Software, boolean satisfiability and reduction.
• nauty, a well-known graph isomorphism solver.
• Optimization Online, an e-Print site for the optimization community.
• The Collection of Computer Science Bibliographies, lots references to CS papers.
• Networked Computer Science Technical Reference Library, CS techreports.
• arXiv.org e-Print archive.
• The NECI Scientific Digital Library, plenty of papers, techreports and theses.
• MathSearch, a search engine for math resources.
• NEOS Guide Optimization Tree, introductory stuff for all fields of optimization.
• Applied Mathematics, a very clear text on linear algebra and related topics.
• Chee K. Yap, "Introduction to Complexity Classes", a text on P, NP, etc.
• Herbert Wilf's Home Page, online math and CS books.
• Optima, the newsletter of the Mathematical Programming Society.
• Leonardo, visualizing programming problems.