P Decision Task
Jump to navigation
Jump to search
A P Decision Task is a computational decision task whose solution time is bounded by a polynomial function.
- Example(s):
- Given a connected graph G, can its vertices be colored using two colors so that no edge is monochromatic.
- …
- Counter-Example(s):
- an NP Task.
- See: P vs NP Problem.
References
2013
- (Wolfram Math World, 2013) ⇒ http://mathworld.wolfram.com/NP-Problem.html
- QUOTE: A P-problem (whose solution time is bounded by a polynomial) is always also NP. If a problem is known to be NP, and a solution to the problem is somehow known, then demonstrating the correctness of the solution can always be reduced to a single P (polynomial time) verification. If P and NP are not equivalent, then the solution of NP-problems requires (in the worst case) an exhaustive search.
2009
- (Fortnow, 2009) ⇒ Lance Fortnow. (2009). “The Status of the P versus NP Problem.” In: Communications of the ACM, 52(9).
- QUOTE: Suppose we have a large group of students that we need to pair up to work on projects. We know which students are compatible with each other and we want to put them in compatible groups of two. We could search all possible pairings but even for 40 students we would have more than 300 billion trillion possible pairings.
In 1965, Jack Edmonds12 gave an efficient algorithm to solve this matching problem and suggested a formal definition of “efficient computation” (runs in time a fixed polynomial of the input size). The class of problems with efficient solutions would later become known as P for “Polynomial Time”.
- QUOTE: Suppose we have a large group of students that we need to pair up to work on projects. We know which students are compatible with each other and we want to put them in compatible groups of two. We could search all possible pairings but even for 40 students we would have more than 300 billion trillion possible pairings.