Computational Complexity & Hardness

← Back to Domain-Specific Families

Abstractions about classifying computational difficulty and its limits — complexity classes and time bounds (complexity class, NTIME, QMA, strongly-polynomial time), foundational impossibility results (P versus NP, Rice's theorem, FLP impossibility), and reduction or hardness techniques such as pseudo-polynomial transformation and computational hardness assumptions.

17 abstractions in this family — domain-specific abstractions that sit near one another in structural-signature space (k-means over structural-signature embeddings). Each is shown with its short description.

• Complexity Class — Sort computational problems into a small lattice of named strata — P, NP, PSPACE, and their kin — by the resource bound they admit under a fixed model, so that placing a problem by one reduction transitively imports its whole feasibility profile.
• Computational hardness assumption — A conjectured computational problem difficulty used as the security foundation of a cryptosystem.
• Cook–Levin Theorem — The theorem that Boolean satisfiability is NP-complete because every NP decision problem has a polynomial-time truth-preserving reduction to SAT.
• FLP Impossibility — Prove that no deterministic algorithm can guarantee both agreement and termination for consensus in an asynchronous system with even one crash-fault — by showing an adversarial message schedule can keep the system perpetually undecided.
• Fourier–Motzkin Elimination — Project a finite system of linear inequalities onto fewer variables by separating one variable's lower and upper bounds and emitting every cross-bound consistency inequality.
• Murphy's Law — The reliability-engineering posture that any physically permitted failure mode will eventually occur, so design must substitute 'permitted' for 'likely' — flipping the burden of proof onto anyone who would leave a permitted mode undefended, and driving enumerate-and-defend discipline.
• Negation as Failure — Treat a ground goal's finite, exhaustive proof failure under a declared logic program and search semantics as defeasible support for weak default negation, while preserving nonmonotonicity, nontermination, floundering, and classical-negation boundaries.
• Nonelementary Problem — A decidable decision problem whose inherent worst-case resource needs exceed every fixed-height exponential-tower bound.
• NP-Equivalent — A decision or output problem that is both NP-hard and NP-easy under polynomial-time Turing reductions.
• NTIME — NTIME(f(n)) is the complexity class of decision problems solvable by a nondeterministic Turing machine within O(f(n)) steps, with NTIME denoting the corresponding time-bounded nondeterministic hierarchy.
• P versus NP Problem — Ask whether every problem whose solutions can be verified in polynomial time can also be solved in polynomial time — turning the apparent gap between checking and finding into the open question of whether it is a structural barrier (P ≠ NP) or mere ignorance (P = NP).
• PPP (complexity) — The class of total polynomially verifiable search problems reducible by efficient witness-preserving maps to the zero-preimage-or-collision PIGEONHOLE CIRCUIT problem.
• Probabilistic argumentation — Probabilistic argumentation is a family of formal systems that attach probabilistic uncertainty to arguments, premises, attacks, supports, or conclusions and define how that uncertainty affects acceptability or inference.
• Pseudo-polynomial transformation — Map instances between numerical decision problems while preserving yes/no membership and polynomially controlling computation, encoding growth, and the target's largest numerical parameter.
• QMA — QMA is a recurring computational complexity, quantum computing identity in which polynomial-size quantum witnesses are verified in quantum polynomial time with bounded completeness and soundness error.
• Rice's Theorem — Every non-trivial semantic property of programs — anything depending on the input-output function rather than the source text — is undecidable, proved by a generic reduction from the halting problem, so no exact analyzer for such a property can exist.
• Strongly-polynomial time — A complexity notion requiring polynomially many arithmetic operations independent of numeric magnitudes.