Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Computability and complexity"

m (→‎P)
m
 
(One intermediate revision by the same user not shown)
Line 1: Line 1:
−
== Classes ==
+
Questions of '''computability''' and '''computational complexity''' are those which concern the limits of [[algorithm]]s to solve certain types of problems under certain constraints.  Any algorithmic question can be placed into one or more [[complexity class]]es, depending on a number of factors such as the speed of the fastest possible solution under a given model of computation.  This article is for background and definitions of such models of computation ([[Turing machines]], [[finite automata]], or the like) and associated complexity classes ([[P (complexity) | P]], [[NP]], [[decidability | undecidable]], etc.)
−
Computability is divided into 2 compelxity classes, namely P and NP.  For all problems in the P class, there exists a known algorithm to solve the problem in a reasonable amount of time.  By this, it is meant that the algorithm will terminate within the time given by some polynomial <math>P(n)</math>, where <math>n</math> is the number of elements in the set being examined.  In contrast, if a problem is NP, then there is no known algorithm to solve it in a reasonable amount of time.
 
  
 +
==See Also==
 +
* [[P versus NP]]
  
−
== P ==
+
{{stub}}
−
Within P, the computational complexity of problems is defined based on the highest degree term in the polynomial <math>P(n)</math>, and is represented using Big-Oh notation.  For example if <math>P(n)</math> has degree <math>5</math>, then <math>P(n) \in O(n^5)</math>.  More formally, if <math>f(x) \in O(g(x))</math>, then <math>\exists C \in \mathbb{R}</math> such that <math>|f(x)| <= C|g(x)|</math> as <math>x -> a</math>, for some <math>a</math> being specified.  Thus, <math>f(x)</math> is bounded by <math>g(x)</math>.
 
−
 
 
−
== NP ==
 
−
NP problems take longer to solve and are not bounded by any polynomial.  Examples include <math>f(n) \in O(2^n)</math>.  A subset of NP problems are NP complete problems.  They have the special property that the rearrangement of any one of them can yield another NP problem.  Thus, if a polynomial time algorithm is found for any NP complete problem, then the conclusion will be that all NP problems are actually P problems, and therefore P = NP.  This is currently one of the Millenium problems for which The Clay Mathematics Institute is offering a $1 million prize for a solution.
 

Latest revision as of 11:24, 6 July 2007

Questions of computability and computational complexity are those which concern the limits of algorithms to solve certain types of problems under certain constraints. Any algorithmic question can be placed into one or more complexity classes, depending on a number of factors such as the speed of the fastest possible solution under a given model of computation. This article is for background and definitions of such models of computation (Turing machines, finite automata, or the like) and associated complexity classes ( P, NP, undecidable, etc.)

See Also

This article is a stub. Help us out by expanding it.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Computability_and_complexity&oldid=15350"