Part 7/14:
- Decidability concerns whether a particular algorithm terminates — that is, whether it arrives at an answer, or runs forever without resolution.
These concepts—tractability, provability, and decidability—are foundational in understanding the security of cryptography, especially encryption standards such as AES. Breaking encryption, like AES-192, is an intractable problem under current knowledge; that is, it requires an exponential amount of computational effort, making real-world decryption infeasible.
The P vs NP Dilemma and Its Cryptographic Consequences
A pivotal question in computer science is: Does P equal NP?
- P problems are solvable in polynomial time—meaning solutions can be found efficiently as problem sizes grow.