搜索
1引言1.1什么事复杂性理论？复杂性理论—是提供给不了解现实世界的理论家的方法或是现代计算机科学的中心话题？引言部分，作为计算机科学的一个活跃领域，将介绍复杂性理论中对算法的应用和发展相关的一些结果。通过学习，我们能深入了解一些重要优化问题的结构，同时拓展了对带有适当资源的算法“可能”的边界。鉴于这本书也是专门为不想把复杂性理论作为他们专业的读者而写，将省略和算法应用不相关的部分。复杂性理论的领域一方面是有效算法的设计和分析，另一方面从两个相反面考虑可解问题。一个有效算法能直接应用求解问题，本身就是有效求解问题的一个证明。相反，复杂性理论的目标是证明难问题在有限资源的前提下是无法解决的。带有坏消息的人很少受欢迎，所以相对于解决某一重要问题的好的算法而言，复杂性理论方面的结果更难沟通。研究复杂性问题的人经常被问到如下问题：为什么你乐于给出某一问题是演算困难的证明，给出一个有效的算法解不是更好么；这些结果有什么用？对我的某一实际应用问题我需要一个算法解。现在我做了什么？显然，证明问题的有效算法可解性更可取，但是否能做到不取决于我们。但我们对这个游戏的规则达成一致时，每个问题都会有一个算法复杂性。复杂性理论和算法理论都在努力估计上述算法复杂性，进而“发现真相”。从这一点上看，证明某一问题不是有效可解的成就感，就像设计了一个有效算法一样，或像发现了比真实算法复杂性更多的内容成就感。