本论文从密码学实践视角出发，系统性地研究了短描述（如密钥、证书）的“可验证复杂性”问题。在密码协议中，密钥或证书通常要求能够在有限时间（多项式时间）内完成展开或验证，否则一个紧凑表示即使理论上存在，也无法在实际有界时间协议中提供操作保障。作者形式化定义了“见证复杂性”（witness complexity）γ(x)，即字符串在通用图灵机上几乎所有最短描述的最小运行时间。γ(x)与香农熵和Kolmogorov复杂度KC有本质区别：低KC未必意味着低γ；可能存在KC很低但γ很高的字符串（例如需要超多项式时间才能展开的描述）。论文证明了γ(x)在多项式因子下具有不变性；并且基于P≠NP假设，给出了条件分离结果；同时利用KC的不可计算性得到了无条件下界。进一步，通过对类相关变体γ_P的表征，证明了γ(x)完全刻画了P与NP的关系（即P=NP当且仅当γ_P可多项式时间计算）。对于结构化的NP族，论文展示了多项式时间可计算性。第二部分发展了伴随度量，并证明了文法大小与推导代价之间的无条件差距，从而将γ(x定位为衡量密钥和证书实用性的关键指标。该工作为密码学中“短但不可用”的描述提供了理论工具，有助于理解哪些紧凑表示能在有界时间内可靠使用。