take a linear program and add one word — integer — and the complexity class jumps from polynomial to NP-hard. that word buys expressive power nothing continuous can match: yes/no decisions, either/or logic, fixed costs, sequencing, assignment. integer programming is the lingua franca of operations research precisely because “decide” is not a convex verb. 𐃏
Np-Hard
Complexity Classes
The Computational Zoo is far more subtle and complex than I thought it was.
Computational Zoo
It contains P, NP (+complete), EXP, NP-hard, CO-NP (+complete), PSPACE, BPP, BQP, EXPSPACE, 2-EXP, halting problem, decidable, etc!
Big Oh Notation
Big-Oh ( \(O\) ) gives an upper bound on how an algorithm’s resource consumption grows with input size \(n\).
explained!
Backlinks (2)
1. Wiki /wiki/
Knowledge is a paradox. The more one understand, the more one realises the vastness of his ignorance.