OurBigBook
.com (beta)
About
$ Donate
Sign in
Sign up
by
Ciro Santilli
(@cirosantilli,
32
)
NP-complete
A problem that is both
NP
and
NP-hard
.
Table of contents
Cook-Levin theorem
P versus NP problem
Ladner's Theorem
P versus NP problem
Cook-Levin theorem
NP-complete
P versus NP problem (P vs NP)
NP-complete
Interesting because of the
Cook-Levin theorem
: if only a single
NP-complete
problem were in
P
, then all NP-complete problems would also be P!
We all know the answer for this: either false or
independent
.
Ladner's Theorem
P versus NP problem
Ancestors
NP
EXPTIME
ELEMENTARY
Complexity class
Computational problem
Computer science
Computer
Information technology
Area of technology
Technology
Index
Incoming links
AGI-complete
BQP
Integer factorization
NP-intermediate
P versus NP problem
Discussion (0)
Subscribe (1)
Sign up
or
sign in
create discussions.
There are no discussions about this article yet.
View article source