Some goals of a definition:
- A great definition should capture some phenomenon, like computation (Turing machines), efficient computation (P), efficient quantum computation (BQP). Cryptography has produced some of the best (and worst) definitions to capture security concerns.
- A great definition should be simple. Defining computability by a Turing machine--good. Definition computability by by the 1334 page ISO/IEC 14882:2011 C++ standard--not so good.
- A great definition should be robust. Small changes in the definition should have little, or better, no change in what fulfills the definition. That is what makes the P v NP problem so nice since both P and NP are robust to various different models of computing. Talking about the problems solvable by a 27-state Turing machine--not robust at all.
- A great definition should be logically consistent. Defining a set as any definable collection doesn't work.
- A great definition should be easy to apply. It should be easy to check that something fulfills the definition, ideally in a simply constructive way.
A great definition drives theorems not the other way around.
Sometimes you discover that a definition does not properly capture a phenomenon--then you should either change or discard your definition, or change your understanding of the phenomenon.
Let's go through an interesting example. In 1984, Goldwasser, Micali and Rackoff defined $k$-bits of knowledge interactive proof systems. Did they have good definitions?
- The definition of interactive proof systems hits all the right points above and created a new area of complexity that we still study today.
- Their notion of zero-(bits of) knowledge interactive proofs hits nearly the right points. Running one zero-knowledge protocol followed by another using the GMR definition might not keep zero-knowledge but there is an easy fix for that. Zero-knowledge proof systems would end up transforming cryptography.
- Their notion of k-bit knowledge didn't work at all. Not really robust and a protocol that output the factors of a number half the time leaked only 1-bit of knowledge by the GMR definition. They smartly dropped the k-bit definition in the journal version.