Lexicon

A growing collection of terms and concepts. These definitions are updated and revised as my understanding evolves.

algorithm

1. P = NP?

   • P: Problems solvable in polynomial time
   • NP: Problems verifiable in polynomial time

   The question asks whether P = NP: Does the ability to efficiently verify a solution guarantee the ability to efficiently find that solution from scratch?

   From first principles, generating novel information appears fundamentally more computationally expensive than recognizing it. Cryptography is predicated on this asymmetry. It is computationally cheap to verify a digital signature, but prohibitively expensive to forge one.

   If P = NP, this asymmetry is an illusion. It implies that structural difficulty does not inherently exist. Any problem where we can efficiently recognize a correct answer would also possess an efficient algorithm to construct that answer.

computability

1. Turing completeness

   A system is Turing complete if it can execute any computable algorithm given unlimited time and unbounded memory.

   To achieve this, a system needs:

   • Conditional branching / Decision mechanism (e.g. `if/else`)
   • Unbounded repetition mechanism (e.g. loops)
   • Unbounded state/memory manipulation (reading and writing intermediate data)