Computational Problems
Computational problems are formal questions defined by a set of valid inputs and their corresponding desired outputs, examined through the lens of algorithmic solvability and resource requirements. Unlike pure mathematics, which asks whether solutions exist, computational theory asks whether solutions can be found through mechanical procedures (algorithms) and at what cost in time, memory, and other resources. This distinction is fundamental to computer science and cryptography, where theoretical possibility often differs significantly from practical feasibility.
Classification and Complexity
Computational problems are typically organized into complexity classes that describe their inherent difficulty. The most widely studied classes include P (problems solvable in polynomial time), NP (problems whose solutions can be verified in polynomial time), and NP-complete (the hardest problems in NP, to which all other NP problems can be reduced). Other important classes address different resource constraints, such as PSPACE (bounded memory) or BQP (quantum computation). Understanding which class a problem belongs to determines whether it has a tractable solution or whether approximations and heuristics are necessary in practice.
Role in Cryptography
Computational problems are central to cryptographic security. Many encryption schemes rely on problems believed to be computationally hard—such as integer factorization or the discrete logarithm problem—where finding solutions requires infeasible amounts of computation despite their mathematical definition being straightforward. The security of these systems depends on the gap between the ease of verification (checking a proposed solution) and the difficulty of solving from scratch. Should more efficient algorithms be discovered, the security guarantees would collapse, making the study of computational hardness essential to cryptographic design.