非确定性：天使与恶魔的算法哲学

本文探讨了非确定性在形式化方法和计算机科学中的两种对立形式：天使性非确定性和恶魔性非确定性。天使性非确定性意味着系统总能选择最佳路径，只要存在一条满足条件的路径，属性即成立；而恶魔性非确定性则相反，系统总选择最坏路径，只要有一条路径违反属性，系统即错误。文章通过P与NP的复杂度分析，说明了天使性非确定性在算法设计和编程语言中的应用，如正则表达式、逻辑编程和约束求解。同时指出，尽管P和NP在理论上存在对应关系，但实际计算中仍面临性能挑战。作者还提到，声明性语言常包含非确定性抽象，但其底层实现细节可能影响性能优化。