The class P consists of decision problems that can be solved in polynomial time relative to the input length.
NP: A class of decision problems where positive instances (evidence that a problem is true) can be verified in polynomial time.
- Demonstrates completeness.
- For example, in the three-coloring problem, the evidence (a graph that can be colored) can be verified in polynomial time to see if it is correctly colored.
- (Soundness = verifying false requires checking all evidence)
NP-hard: The most “difficult” problems.
- If problem A can be reduced to problem B, the difficulty of A is less than or equal to the difficulty of B.
- (The input transformation during reduction must be done in polynomial time)
- NP-complete problems can be reduced to each other.
- Being NP-hard does not necessarily mean being in NP.
NP-complete: Problems that are both in NP and NP-hard.
It is known that P is a subset of NP.
-
Algorithms are equivalent to Turing Machines.
- Turing machines only make local changes. (locality)
-
If P = NP, all NP-complete problems can be solved in polynomial time.
- This would have a significant impact on mathematical proof problems.
-
If P != NP, it has a smaller impact, but it is related to cryptography.
- RSA encryption, for example, relies on the assumption that factoring large numbers cannot be efficiently solved (which is an NP problem but not a P problem).
- If P != NP, it would be proven that there are problems that can be easily verified but hard to find the answer to.
-
From Impagliazzo’s five possible worlds, we want to know which one is our world.
- That is the theme of this field.
I thought that the approach of considering the relationship and classification of problems could be applied in other fields as well. (blu3mo) #ComputerScience (Expert in Computer Science)