无向图中的最小割
Minimum Cut in undirected graphs
我想引用 Wikipedia
In mathematics, the minimum k-cut, is a combinatorial optimization
problem that requires finding a set of edges whose removal would
partition the graph to k connected components.
如果边的集合是最小的，则称为最小割。
对于 k = 2，这意味着找到一组边，删除这些边会 断开 将图分成 2 个 连接的 组件。
然而，维基百科的同一篇文章说：
For a fixed k, the problem is polynomial time solvable in O(|V|^(k^2))
我的问题是，这是否意味着最小 2-cut 是一个属于复杂度 class P 的问题？
min-cut 问题可以在多项式时间内解决，因此是的，它确实属于复杂性 class P。与此特定问题相关的另一篇文章是 Max-flow min-cut theorem.
首先，算法的时间复杂度应该通过将算法需要完成的步骤数表示为输入的长度的函数来评估（参见Time complexity).或多或少正式地说，如果您改变输入的长度，算法完成所需的步骤数将如何变化？
其次，算法的时间复杂度与算法解决的问题属于什么复杂度class并不完全相同。对于一个问题，可以有多种算法来解决它。 P中的素性测试问题（即测试一个数是否为素数），但实践中使用的一些（大多数）算法实际上不是多项式的。
第三，在大多数算法的情况下，您会在 Internet 上找到评估时间复杂度的定义，而不是根据定义完成的（即不是作为输入长度的函数，至少不是直接表示为这样的）。让我们采用古老的朴素素性测试算法（您将 n 作为输入并检查除以 2,3...n-1 的算法）。这个算法需要多少步？一种表达方式是 O(n) 步。这是对的。那么这个算法是多项式的吗？好吧，它在 n 中是线性的，所以它在 n 中是多项式的。但是，如果您看一下时间复杂度的含义，该算法实际上是指数级的。首先，问题的输入长度是多少？好吧，如果您提供输入 n 作为位数组（实践中通常如此），那么输入的长度粗略地说就是 L = log n。因此，您的算法需要 O(n)=O(2^log n)=O(2^L) 个步骤，因此在 L 中呈指数级增长。因此，朴素素性测试在 n 中同时呈线性，但在输入 L 中呈指数增长。两者都正确。顺便说一句，AKS 素数测试算法在输入大小上是多项式的（因此，素数测试问题在 P）。
第四，首先什么是P？好吧，这是一个 class 的问题，包含所有 决策问题 可以在多项式时间内解决。什么是决策问题？可以用是或否回答的问题。查看这两个维基百科页面了解更多详情：P (complexity) and decision problems.
回到你的问题，答案是否定的（但非常接近是：p）。如果表述为决策问题，则最小 2-cut 问题在 P 中（您的表述需要的答案不仅仅是是或否）。同时，在 O(|V|^4) 步中解决问题的算法是输入大小的多项式算法。为什么？好吧，问题的输入是图（即顶点、边和权重），为简单起见，假设我们使用 adjacency/weights 矩阵（即输入的长度至少是 [=22= 的二次方） ]).因此，在 O(|V|^4) 步中解决问题意味着输入大小的多项式。实现这一点的算法证明了最小 2-cut 问题（如果表述为决策问题）在 P.
中
与 P 相关的 class 是 FP 并且您的问题（按照您的表述）属于对此 class.
我想引用 Wikipedia
In mathematics, the minimum k-cut, is a combinatorial optimization problem that requires finding a set of edges whose removal would partition the graph to k connected components.
如果边的集合是最小的，则称为最小割。
对于 k = 2，这意味着找到一组边，删除这些边会 断开 将图分成 2 个 连接的 组件。
然而，维基百科的同一篇文章说：
For a fixed k, the problem is polynomial time solvable in O(|V|^(k^2))
我的问题是，这是否意味着最小 2-cut 是一个属于复杂度 class P 的问题？
min-cut 问题可以在多项式时间内解决，因此是的，它确实属于复杂性 class P。与此特定问题相关的另一篇文章是 Max-flow min-cut theorem.
首先，算法的时间复杂度应该通过将算法需要完成的步骤数表示为输入的长度的函数来评估（参见Time complexity).或多或少正式地说，如果您改变输入的长度，算法完成所需的步骤数将如何变化？
其次，算法的时间复杂度与算法解决的问题属于什么复杂度class并不完全相同。对于一个问题，可以有多种算法来解决它。 P中的素性测试问题（即测试一个数是否为素数），但实践中使用的一些（大多数）算法实际上不是多项式的。
第三，在大多数算法的情况下，您会在 Internet 上找到评估时间复杂度的定义，而不是根据定义完成的（即不是作为输入长度的函数，至少不是直接表示为这样的）。让我们采用古老的朴素素性测试算法（您将 n 作为输入并检查除以 2,3...n-1 的算法）。这个算法需要多少步？一种表达方式是 O(n) 步。这是对的。那么这个算法是多项式的吗？好吧，它在 n 中是线性的，所以它在 n 中是多项式的。但是，如果您看一下时间复杂度的含义，该算法实际上是指数级的。首先，问题的输入长度是多少？好吧，如果您提供输入 n 作为位数组（实践中通常如此），那么输入的长度粗略地说就是 L = log n。因此，您的算法需要 O(n)=O(2^log n)=O(2^L) 个步骤，因此在 L 中呈指数级增长。因此，朴素素性测试在 n 中同时呈线性，但在输入 L 中呈指数增长。两者都正确。顺便说一句，AKS 素数测试算法在输入大小上是多项式的（因此，素数测试问题在 P）。
第四，首先什么是P？好吧，这是一个 class 的问题，包含所有 决策问题 可以在多项式时间内解决。什么是决策问题？可以用是或否回答的问题。查看这两个维基百科页面了解更多详情：P (complexity) and decision problems.
回到你的问题，答案是否定的（但非常接近是：p）。如果表述为决策问题，则最小 2-cut 问题在 P 中（您的表述需要的答案不仅仅是是或否）。同时，在 O(|V|^4) 步中解决问题的算法是输入大小的多项式算法。为什么？好吧，问题的输入是图（即顶点、边和权重），为简单起见，假设我们使用 adjacency/weights 矩阵（即输入的长度至少是 [=22= 的二次方） ]).因此，在 O(|V|^4) 步中解决问题意味着输入大小的多项式。实现这一点的算法证明了最小 2-cut 问题（如果表述为决策问题）在 P.
与 P 相关的 class 是 FP 并且您的问题（按照您的表述）属于对此 class.