An exploration of two contrasting models of nondeterminism in computer science: demonic nondeterminism (worst-case path, used in formal methods and safety verification) and angelic nondeterminism (best-case path, foundational to complexity classes like NP and declarative language semantics). The piece explains how NP is defined via angelic nondeterminism, illustrates it with SAT and list membership examples, and connects it to declarative languages like SQL, regex, and logic programming. It also touches on why features that expose the underlying deterministic implementation are frustrating in declarative contexts, and briefly mentions probabilistic 'eldritch' nondeterminism beyond both models.
2 Impressions