P vs NP

P vs NP is the most important problem in computer science. And it is one of the Millennium Prize Problems.

• P: solvable in polynomial time

• NP: verifiable in polynomial time
• NP-complete: in NP and also NP-hard (the hardest problem in NP)
  • SAT, 3-SAT, 3-coloring...
  • Cook Levin's theorem proves that every NP problem reduces to SAT
• NP-hard: at least hard as the hardest problem in NP, but might not be in NP

Consequence of Finding a "P" solution for NP problems

Assumption: private -> public is easy, public -> private is impossible. A practical NP solution will break this.

• Bitcoin, SSH rely on public key <-> private key mechanism

• To spend

message = "Spend this coin to Carol, with this fee"
signature = Sign(private_key, message)

• To verify

Verify(public_key, message, signature) == true

Problem Reduction

$a \leq b$

a reduces to b means "if we can solve b, we can solve a".

Let's say $a$ is problem "find the kth largest element in a list of numbers", and $b$ is the problem "sort a list of numbers". Then we can trivially solve $a$ if we can solve $b$.

Example: Vertex Cover & Independent Set

Philosophical Implication

Is judging easier than creating? Search maybe the essence of intelligence Knowledge is not the same as compressed knowledge

Knowledge is not merely the compressed artifact. Knowledge is also the ability to decompress, reconstruct, and use it.