1

例子 ：

if(A & B)
{
    if(C)
    {
    }

    if(D)
    {
    }
}

对于此代码中的所有条件，我们有四种不同的状态。0 代表 False，1 代表真实状态。* 表示条件在此状态流中无效。所以在这种情况下，下面列出了所有可能的状态。

A B C D

0 * * *

1 0 * *

1 1 1 0

1 1 0 1

解释：在第一个状态 (0 * * *) 中，条件 A 为真。因此，B 在代码中没有任何作用。因为在评估 A 本身之后，if 案例失败了。因此条件 C 和 D 也不会被评估。同样，其他三种可能的状态也是如此。

但是有没有任何已经实现的算法，我可以通过它找到特定输入的所有这些状态。因为当我们尝试解决更复杂的嵌套代码时，这会变成一个巨大的复杂问题。我认为编写一个应用程序来给出这样的结果是非常困难的。

如果有人知道某种已经实现的东西可能对我有帮助，请让我知道。

4

1 回答 1

0

我很抱歉成为承载者或坏消息，但由于两个非常著名的原因，这种算法是不可能的。

停机问题

要在图灵完备的语言中解决这个问题，您需要解决 The Halting problem。如果您的示例程序如下所示：

if(A & B & maybeAnInfiniteLoop())
{
    if(C)
    {
    }

    if(D)
    {
    }
}

那么我们将无法从理论上知道函数 mayAnInfiniteLoop 是否终止，因此 C 和 D 是否重要，或者布尔值的唯一有效状态是否为 00* 、10 * 或 01* ，因为 11 * 永远不会完成和 C 和 D 永远不会到达。

NP-完全

现在让我们假设您能够将问题简化为布尔表达式。在只有 IF、AND、OR、NOT 和布尔值的语言子集中，该语言不是图灵完备的。这就是所谓的强归一化。布尔表达式的语言就是这样一种有用语言的一个例子。

然而，即使我们可以保证程序停止，在该语言中决定所有有意义的布尔值状态的算法也是一个NP 完全问题。事实上，它是最著名的。它被称为布尔可满足性问题。请注意，在您的示例中，当 A 或 B 为假时，您说 C 和 D 没有意义。这是因为您知道满足表达式“A&B”的 A 和 B 的唯一值集是 (1,1)。您可以这样做，因为它是一个非常简单的表达式，但是对于一些非常合理的输入，在一般情况下解决此问题的算法可能无法在您的一生中完成。

有希望吗？

P=NP的问题没有已知的答案。事实上，它可能是当今最重要的开放式数学问题。如果 P=NP 那么你很幸运，但我不会让你抱有希望。P 上的聪明钱不等于 NP。

于 2014-03-29T15:08:40.510 回答