Lesson plan
P (complexity)
In computational complexity theory, P, also known as PTIME or DTIME(n O(1) ), is a fundamental complexity class. It contains all decision problems that can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time. Cobham's thesis holds that P is the class of computational problems that are "efficiently solvable" or "tractable". This is inexact: in practice, some problems not known to be in P have practical solutions, and some that are in P do not, but this is a useful rule of thumb.
Article summary
In computational complexity theory, P, also known as PTIME or DTIME(n O(1) ), is a fundamental complexity class. It contains all decision problems that can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time. Cobham's thesis holds that P is the class of computational problems that are "efficiently solvable" or "tractable". This is inexact: in practice, some problems not known to be in P have practical solutions, and some that are in P do not, but this is a useful rule of thumb.
Key claims
- publication date: 2001 — source: Wikipedia · confidence 0.95
- publication date: 1965 — source: Wikipedia · confidence 0.95
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- The record states that the publication date is "2001". What evidence would count against this claim?
- The record states that the publication date is "1965". What evidence would count against this claim?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
- Wikipedia https://en.wikipedia.org/w/index.php?oldid=1333496700
Key claims and bibliography are generated from the same tracked claims and sources as the article page.