*’P’ = ‘NP’*

*the relationship between the complexity classes ‘P’ + ‘NP’ is an unsolved question in ‘theoretical computer science’*

.

(it is considered to be the most important problem in the field)

.

(informally speaking…)

can every problem whose solution can be quickly verified by a computer can also be quickly solved by a computer?

.

in essence, the question P = NP? asks…

(if ‘yes’-answers to a ‘yes’-or-‘no’-question can be verified “quickly” (in ‘polynomial time’), can the answers themselves also be computed quickly?)

.

(consider, for instance, the subset-sum problem, an example of a problem which is “easy” to verify, but whose answer is believed (but not proven) to be “difficult” to compute…)

(given a set of integers, does some nonempty subset of them sum to 0?)

for instance, does a subset of the set {−2, −3, 15, 14, 7, −10} add up to 0?

(the answer “yes, because {−2, −3, −10, 15} add up to zero”, can be quickly verified with 3 additions)

(however, finding such a subset in the first place could take more time)

(the ‘information’ needed to ‘verify’ a ‘positive answer’ is also called a ‘certificate’)

given the right certificates, “yes” answers to our problem can be verified in polynomial time, so this problem is in NP)

(an answer to the P = NP question would determine whether problems like the ‘subset-sum problem’ are as “easy” to compute as to verify)

(if it turned out P does not equal NP, it would mean that some NP problems are substantially “harder” to compute than to verify)

the restriction to “‘yes’ / ‘no’ problem”s is unimportant…

(the resulting question when more complicated answers are allowed (whether FP = FNP) is equivalent)

.

.

(the ‘clay mathematics institute’ has offered a $1 million US prize for the first correct proof)

.

.

*NP-COMPLETE* –>

(in ‘computational complexity theory’, the complexity class NP-complete (abbreviated NP-C or NPC), is a class of problems having 2 properties…)

#1

(any given solution to the problem can be verified quickly (in ‘polynomial time’)

(the set of problems with this property is called NP (‘non-deterministic polynomial time’))

#2

(if the problem can be solved quickly (in ‘polynomial time’), then so can every problem in ‘NP'”)

.

(in ‘computational complexity theory’, NP-hard (‘non-deterministic polynomial-time hard’) is a class of problems that are, informally, “at least as hard as the hardest problems in NP”)

.

.

*👨‍🔬🕵️‍♀️🙇‍♀️*SKETCHES*🙇‍♂️👩‍🔬🕵️‍♂️*

.

📚📖|/\-*WIKI-LINK*-/\|📖📚

.

.

👈👈👈☜*“UNSOLVED PROBLEMS”* ☞ 👉👉👉
*COMPUTER SCIENCE*

.

.

💕💝💖💓🖤💙🖤💙🖤💙🖤❤️💚💛🧡❣️💞💔💘❣️🧡💛💚❤️🖤💜🖤💙🖤💙🖤💗💖💝💘

.

.

*🌈✨ *TABLE OF CONTENTS* ✨🌷*

.

.

🔥🔥🔥🔥🔥🔥*we won the war* 🔥🔥🔥🔥🔥🔥