最少发言次数:P或NP？

Question

编写在1行源代码中完成一项任务的程序是程序员的共同爱好。但这有点微不足道:我可以用1000行代码，删除所有的换行，瞧！1行！

因此，为了使事情有趣，我们可以计数语句。对于C风格的语言来说，计算语句的一种简单方法是计数分号:所以嵌套一百万个if-else是可以的。

假设您有一个程序P和n语句。它通过一个状态序列(变量值) s (其中s是一个向量)并生成输出x。我们可以提出两个问题：

1. 少于n语句的程序能产生输出x吗？
2. 小于n语句的程序能通过的的某些子集吗？

立即，一些事情变得明显起来。参加以下活动：

int sum = a+b;
float mean = sum/2.0;
return mean;

我们可以将(或者应该说是“降级”)重构为一条直线：

return (a+b)/2.0;

每个程序都能分解成一行吗？参加这个项目：

string x = "";
for (int i = 0; i<a; i++)   // Should these semicolons count?
{
    x = x + ".";
}
return x;

这更有挑战性。

这个问题可以通过使用小于n语句的所有可能程序(理论上可以有无限可能值的常量，但没有真正的语言有无限的内存来存储它们，或者有无限的磁盘空间来容纳源代码)来回答。

然而：

A.对于一个程序P，该程序使用n语句生成x (可能通过s)，它可以证明没有qE 238可以在e 139mE 240语句中找到(以有效的方式)？

(以有效的方式)能找到最小的n吗？

是否保证最小n为1？

您可以假设任何您想要的语言，尽管真正的语言会更有趣。如果你的语言不寻常，请在你的语言中给“陈述”下一个定义。

我假设了命令式语言，但欢迎将问题修改为功能语言。

有一个简单的解决方案:对于任何P，运行P并记录x。现在编写一个程序Q，它只打印x。对于有输入的程序，用每个输入映射到一个正确的输出，做一个很长的if- each。

这个解决办法不能令人满意，虽然我不完全确定原因。首先，对于无限可能的输入，这是不可能的(但我已经说过真正的程序是有限的，所以我们可以说真正的输入是有限的)。其次，它只在技术上通过的的一个子集:即空集。第三，这确实是反政府的。

任何帮助定义了这个小聪明的技巧，也是值得赞赏的。

PS:不管我说什么，这都不是家庭作业。我只是对这个问题感到好奇，尽量把它说清楚。当然，我还是会说如果是作业的话，所以.

Answer 1

由于语句的概念是特定于语言的，所以有些语言中每个程序都可以编写成一个语句或表达式。地狱，甚至有语言，每一个程序必须写成一个单一的表达式。

也就是说，假设一种语言不是这样的(而且肯定有这样的语言)，那么找到最小的语句来解决一个给定的问题的问题既不是P的问题，也不是NP的问题--它是不可判定的。

这个问题可以用少于n个语句的所有可能的程序来详尽地回答，这个数是有限的。

由于其中一些程序不会终止，并且不可能知道哪些程序会终止(停止问题)，所以这是行不通的。

在大多数语言中，具有小于n个语句的程序的数量是，而不是有限的。例如，在大多数语言中，表单return foo + bar + ... + baz;有无限多的语句。

如果程序P用n条语句产生x(也许是通过s)，它能证明在m条语句中找不到任何q(以有效的方式)吗？

(我假设你在这里忘记了一个m < n，否则这个问题就没有意义了。)

不，根本无法证明。

B.能否(以有效方式)找到最小n？

不，根本找不到。

是否保证最小n为1？

正如我在开始时所说，这取决于语言，就上述问题而言，我假设一种语言，对此的答案是否定的。