
	Directories \| Web \| Images \| Groups \| News \| Shopping \| Local Enter your search keyword(s):

Home | About | Add your website here

(formerly Encyclopedic directory) Complexity Theory
Home / Top / Computers / Computer Science / Theoretical / Complexity Theory

Edit | Discuss Article

Complexity

There are different senses of complexity:

In information processing, complexity is a measure of the total number of properties transmitted by an object and detected by an observer. Such a collection of properties is often referred to as a state.
In computer science, the study of how much time and memory a computer algorithm may take is the field of computational complexity theory.
Complexity is often used as a shorthand for the field that developed in the late 1980s around the use of mathematical and computational modeling of biological, economic and technological systems known as "complex systems" (sometimes complex adaptive systems).
In the sense of how complicated a problem is from the perspective of the person trying to solve it, limits of complexity are measured using a term from cognitive psychology, namely the hrair limit.
In mathematics, Krohn-Rhodes complexity is an important topic in the study of finite semigroups.

See also Important publications in complexity
Source | Copyright

Webmasters: Add your website here:

Readers: Edit | Discuss Listings

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.
http://www.cs.washington.edu/homes/kautz/blackbox/

Average-Case Complexity Forum
Introduction and survey papers.
http://www.uncg.edu/mat/avg.html

The P versus NP Problem
Description of the P vs NP question, designated a Clay Mathematics Institute Millennium Prize Problems, by Stephen Cook.
http://www.claymath.org/prize_problems/p_vs_np.htm

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

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.
http://www.eccc.uni-trier.de/eccc/

Roberto Bayardo's Resources
Includes the relsat SAT solver and related papers.
http://www.almaden.ibm.com/cs/people/bayardo/resources.html

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

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.
http://www.intellektik.informatik.tu-darmstadt.de/SATLIB/

Stas Busygin's NP-Completeness Page
A proposal for solving NP-hard problems.
http://www.busygin.dp.ua/npc.html

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

Information-based Complexity
People, publications, prizes.
http://www.ibc-research.org/

Algorithms and Complexity
A collection of bookmarks by Heribert Vollmer.
http://www-info4.informatik.uni-wuerzburg.de/personen/ehemalig/vollmer/tcs-bookmarks.html

Constraint Satisfaction Problems
Research group in the Computing Laboratory, Oxford University.
http://web.comlab.ox.ac.uk/oucl/research/areas/constraints/index.html

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

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

Algorithms and Complexity Research Area
The Oxford University Computing Laboratory's area on Algorithms and complexity, with links to lectures and information.
http://web.comlab.ox.ac.uk/oucl/research/areas/algs/

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

Algorithms and Complexity
An overview of computational models and methods and how they relate to complexity, with links to selected papers.
http://www.almaden.ibm.com/cs/k53/algo.html

Computational Complexity Theory
Wikipedia article.
http://en.wikipedia.org/wiki/Computational_complexity_theory

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

Computational Complexity Theory
Definition of the subject, links.
http://www.cs.umass.edu/~immerman/complexity_theory.html

P vs NP
Official version of the million dollar open problem in Theoretical Computer Science by the Clay Mathematical Institute.
http://www.claymath.org/millennium/P_vs_NP/

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

Lecture notes on Complexity
Collection of lecture notes by Prof. Eric Allender, Rutgers University.
http://athos.rutgers.edu/~allender/lecture.notes/

Help build the largest human-edited directory on the web.

Submit a Site - Open Directory Project (modified) - Become an Editor