计算复杂性理论简介

2024 年 8 月 28 日 | 阅读 6 分钟

概述

计算复杂性理论研究算法和问题的复杂性。它的目标是确定解决问题所需的计算资源，例如时间、空间或通信，并确定算法效率的局限性和可能性。

计算复杂性理论中最重要的概念之一是 P 与 NP 问题，它询问是否可以在多项式时间内验证的每个问题也可以在多项式时间内解决。P 类包含可以在多项式时间内解决的问题，而 NP 类包含可以在多项式时间内验证解决方案的问题。

NP 完全问题是 NP 问题的一个特殊子集，人们认为它是该类中最难的问题之一，因为任何 NP 完全问题都可以在多项式时间内简化为任何其他 NP 完全问题。NP 完全性的概念对密码学、优化以及计算机科学和数学的许多其他领域具有重要意义。

计算复杂性理论中的其他重要概念包括多项式时间归约的概念，它允许将一个问题的复杂性与另一个问题进行比较，以及 P 和 NP 之外的复杂性类，例如 PSPACE 和 EXPTIME。

总的来说，计算复杂性理论是一个丰富而重要的研究领域，它为理解算法和问题的计算限制和可能性提供了一个框架。

可解问题与不可解问题

在计算复杂性理论中，问题通常根据是否存在可以解决问题的算法被分类为可解或不可解。

可解问题 - 如果存在一种算法可以在有限的时间内解决该问题，则称该问题是可解的，即，对于问题的任何输入，该算法可以在有限的步骤内产生正确的输出。例如，查找两个整数之和的问题是可解的，因为存在一个简单的算法可以在有限的步骤内将两个整数相加。
不可解问题 - 另一方面，如果不存在任何算法可以在有限的时间内解决该问题，则称该问题是不可解的。一个众所周知的不可解问题是停机问题，它询问给定的程序最终会停止还是永远运行。已经证明，没有算法可以解决所有可能输入的停机问题。

重要的是要注意，不可解问题与难题不同。有些问题可能是可解的，但需要指数级的时间或空间来解决，这使得它们在实际应用中对于大型输入规模来说是不可行的。计算复杂性理论的研究侧重于理解算法效率的局限性，并确定哪些问题是可解的，哪些问题是不可解的，以及哪些问题是可解的但不可行的。

可判定问题与不可判定问题

在计算复杂性理论中，可解问题也经常根据是否存在可以判定问题的算法被分类为可判定或不可判定。

可判定问题 - 如果存在一种算法可以在有限的时间内确定问题的实例是“是”实例还是“否”实例，则称该问题是可判定的。换句话说，该算法将始终停止并返回正确的答案，无论是“是”还是“否”。例如，确定给定数字是否为素数的问题是可判定的，因为存在一种算法可以在有限的时间内确定数字的素性。
不可判定问题 - 另一方面，如果不存在任何算法可以在有限的时间内确定问题的实例是“是”实例还是“否”实例，则称该问题是不可判定的。不可判定问题的经典例子是停机问题，它询问给定的程序最终会停止还是永远运行。已经证明，没有算法可以解决所有可能输入的停机问题。

值得注意的是，不可判定性是一个比不可解性更强的概念。所有不可判定问题都是不可解的，但并非所有不可解问题都是不可判定的。例如，找到旅行商问题的最优解对于大型输入规模来说是不可解的，但它仍然是可判定的，因为存在一些算法可以在有限的时间内找到次优解。

对可判定和不可判定问题的研究对于理解算法可解性的局限性，以及确定计算机科学和其他领域中自动化决策的范围和局限性非常重要。

P 与 NP 问题

在计算复杂性理论中，可判定问题也经常被分类为 P 或 NP 问题。

P 与 NP 问题是计算机科学和数学中最著名的未解决问题之一。它询问是否可以在多项式时间内验证的每个问题也可以在多项式时间内解决。换句话说，如果可以有效地（在多项式时间内）检查问题的解决方案，那么也可以有效地（在多项式时间内）找到它吗？

可以在多项式时间内解决的问题类被称为 P，而可以在多项式时间内验证的问题类被称为 NP。许多重要的计算问题已知属于 NP，包括旅行商问题、背包问题和可满足性问题。

P 与 NP 问题对密码学、优化以及计算机科学和数学的其他领域具有重要意义。如果 P = NP，那么解决许多重要的计算问题可能会比目前已知的效率更高，这可能会对密码学和数据分析等领域产生重大影响。但是，如果 P ≠ NP，那么许多重要的计算问题可能从根本上难以解决，这可能会对自动化决策的限制产生重要影响。

尽管经过数十年的研究，P 与 NP 问题仍然是计算机科学和数学中最具挑战性的未解决问题之一，目前尚不清楚它是否会在近期内得到解决。