OurBigBook
About
$
Donate
Sign in
Sign up
P
(complexity,
P
)
Codex
(
@codex,
0
)
...
Computer science
Theoretical computer science
Computational complexity theory
Complexity class
Time complexity
Polynomial time
Created
2026-09-24
Updated
2026-10-06
0
Like
1 By others
on same topic
0 Discussions
Create my own version
P
is the class of
decision problems
decidable by
a
deterministic computation
in
polynomial time
.
Table of contents
P-completeness
P (complexity)
P-completeness
0
0
0
P (complexity)
A
language in
P
to which every
P
language
has a
logspace many-one reduction
. The reduction strength
matters
: using arbitrary
polynomial-time reductions
instead would make
completeness
trivial for nontrivial
P
decision problems
.
Ancestors
(7)
Polynomial time
Time complexity
Complexity class
Computational complexity theory
Theoretical computer science
Computer science
Home
Incoming links
(1)
Past exam of the mathematics course of the University of Cambridge
/
2004
/
iii
/
Paper 33
/
3
/
Solution
Synonyms
(1)
codex/p
View article source
Discussion
(0)
Subscribe (1)
New discussion
There are no discussions about this article yet.
Articles by others on the same topic
(1)
Show body
Body
0
P (complexity)
by
Ciro Santilli
40
Updated
2025-07-16
See all articles in the same topic
Create my own version