Context
The relation between the complexity classes P and NP is studied in computational complexity theory, the part of the theory of computation dealing with the resources required during computation to solve a given problem. The most common resources are time (how many steps it takes to solve a problem) and space (how much memory it takes to solve a problem).
In such analysis, a model of the computer for which time must be analyzed is required. Typically such models assume that the computer is deterministic (given the computer's present state and any inputs, there is only one possible action that the computer might take) and sequential (it performs actions one after the other).
In this theory, the class P consists of all those decision problems (defined below) that can be solved on a deterministic sequential machine in an amount of time that is polynomial in the size of the input; the class NP consists of all those decision problems whose positive solutions can be verified in polynomial time given the right information, or equivalently, whose solution can be found in polynomial time on a non-deterministic machine. Clearly, P ⊆ NP. Arguably the biggest open question in theoretical computer science concerns the relationship between those two classes:
- Is P equal to NP?
In a 2002 poll of 100 researchers, 61 believed the answer to be no, 9 believed the answer is yes, and 22 were unsure; 8 believed the question may be independent of the currently accepted axioms and therefore is impossible to prove or disprove.
Read more about this topic: P Versus NP Problem
Famous quotes containing the word context:
“The hard truth is that what may be acceptable in elite culture may not be acceptable in mass culture, that tastes which pose only innocent ethical issues as the property of a minority become corrupting when they become more established. Taste is context, and the context has changed.”
—Susan Sontag (b. 1933)
“Among the most valuable but least appreciated experiences parenthood can provide are the opportunities it offers for exploring, reliving, and resolving one’s own childhood problems in the context of one’s relation to one’s child.”
—Bruno Bettelheim (20th century)
“Parents are led to believe that they must be consistent, that is, always respond to the same issue the same way. Consistency is good up to a point but your child also needs to understand context and subtlety . . . much of adult life is governed by context: what is appropriate in one setting is not appropriate in another; the way something is said may be more important than what is said. . . .”
—Stanley I. Greenspan (20th century)