Directory of Complexity Theory Resources

Home > Computers > Computer Science > Theoretical > Complexity Theory

The study of algorithmic complexity. A topic of particular interest is the relationship between polynomial-time (P) and non-deterministic polynomial-time (NP), the latter consisting of algorithms for which there is a P solution given the right initial guess (often called witness or certificate).

Subcategories

• Conferences
• People
• Publications

Resources in This Category

• A Compendium of NP Optimization Problems

  http://www.nada.kth.se/~viggo/problemlist/compendium.html
  This is a preliminary version of the catalog of NP optimization problems.

• Complexity of Algorithms

  http://artemis.cs.yale.edu/classes/cs460/Spring98/contents.html
  A list of topics from a Computer Science course involving complexity of algorithms. HTML and PS format.

• Complexity Theory

  http://www.wisdom.weizmann.ac.il/~oded/cc.html
  Two set of lecture notes by Prof. Oded Goldreich, Weizmann Institute.

• Computability and Complexity

  http://www.csc.liv.ac.uk/~ped/teachadmin/algor/comput_complete.html
  An online course on complexity.

• Computational Complexity and Programming Languages

  http://www.cis.syr.edu/people/royer/talks.html
  Summaries of talks of the DIMACS workshop (July 1996), collected by James Royer.

• Computational Complexity Theory

  http://en.wikipedia.org/wiki/Computational_complexity_theory
  Wikipedia article.

• Computational Complexity Theory

  http://www.cs.bris.ac.uk/Teaching/Resources/COMS30126/
  Course COMS 30126: Computational Complexity Theory, Department of Computer Science, University of Bristol

• Constraint Satisfaction Problems

  http://www.comlab.ox.ac.uk/activities/constraints/
  Research group in the Computing Laboratory, Oxford University.

• ECCC - Electronic Colloquium on Computational Complexity

  http://eccc.hpi-web.de/
  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.

• Efficient algorithms and intractable problems

  http://www-inst.eecs.berkeley.edu/~cs170/fa06/
  Course taught by Christos Papadimitriou and Umesh Vazirani at the University of California at Berkeley.

• IBM Research: Algorithms & Theory

  http://domino.research.ibm.com/comm/research.nsf/pages/r.algorithms.html
  An overview of computational models and methods and how they relate to complexity, with links to selected papers.

• Lecture notes on Complexity

  http://www.cs.rutgers.edu/~allender/lecture.notes/
  Collection of lecture notes by Prof. Eric Allender, Rutgers University.

• Parameterized Complexity

  http://www.cs.mun.ca/~harold/W_hier/W_hier.html
  Brief description, list of workers and problem compendium, compiled by Todd Wareham.

• Probabilistically Checkable Proofs and Approximation

  http://www-cse.ucsd.edu/users/mihir/pcp.html
  Pointers to some survey articles and their authors, by M. Bellare.

• SAT Live!

  http://www.satlive.org/
  A collection of up-to-date links about the satisfiability problem (solvers, benchmarks, articles). A discussion forum is available as well.

 

Home > Computers > Computer Science > Theoretical > Complexity Theory

 

---

 

Thanks to DMOZ, which built a great web directory for nearly two decades and freely shared it with the web. About us