最小陈述数量：P还是NP？

Question

编写完成1行源代码任务的程序是常见的程序员爱好。但是这有点儿微不足道：我可以拿走100万行代码，删除所有换行符，瞧！ 1行！

因此，为了使事情有趣，我们可以计数陈述。对于C风格的语言，计算语句的简单方法是计算分号：因此嵌套一百万个if-elses是很好的。

说你已经有了一个计划P与ň语句。它通过状态的序列（可变值）小号（其中小号是矢量），并产生输出X。我们也可以提出两个问题：

1. 少于ň语句的程序可以产生输出X？
2. 少于ň语句的程序可以顺利通过的小号某个子集？

立即，有些事情变得明显。看看下面的程序：

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

我们可以重构（或者我应该说“defactor”）此为一个衬垫：

return (a+b)/2.0; 

可以每程序defactored一个行？采取这个程序：

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

这是一个更具挑战性。

的问题，可以通过尝试用不到ň语句，这个数字是有限的每一个可能的方案详尽地回答了（理论上可以有无限多的可能值，但没有真正的语言具有无限的内存存储它们或无限的磁盘空间以容纳源代码）。

但是：

A.是否有可能与ň语句来证明一个程序P产生X（也许是通过小号）没有Q可以在做m可以找到语句（以有效的方式）？

B.能否找到（以有效的方式）最低限度的？？

C.最小值n保证为1？

你可以假设你想要的任何语言，但真正的语言会更有趣。如果您的语言不正常，请用您的语言提供“声明”的定义。

我已经假设了命令式语言，但是欢迎对这个问题进行适应性修改。

有一个平凡解：对于任何P，运行P和记录X。现在写一个程序Q哪个简单打印x。对于有输入的程序，在每个输入映射到正确输出的情况下，做一个很长的if-else。

这个解决方案不令人满意，虽然我不完全确定为什么。首先，对于无限可能的投入是不可能的（但是我已经通过说真正的节目是有限的来覆盖我的屁股，所以我们可以说真实的投入是有限的）。其次，它只在技术上通过的子集：即空集。第三，这真的是非常具有挑战性。

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

PS：无论我的话是值得的，这不是作业。我只是对这个问题感到好奇，并试图尽可能清楚地说出这个问题。当然，我仍然会说，如果它是作业，那么...

Answer 1

由于语句的概念是语言特定的，因此有些语言中的每个程序都可以写成单个语句或表达式。地狱，甚至有语言，其中每个程序必须被写成单个表达式。这就是说，假设语言不是这种情况（并且确实存在这样的语言），找到解决给定问题的语句的最小值的问题将既不在P也不在NP中 - 这是不可判定的。

的问题，可以通过尝试用小于n语句每一个可能的方案详尽地回答，这个数字是有限的

由于一些这些程序不会终止，这是不可能知道哪些将（停止问​​题），这是行不通的。

此外，少于n个语句的程序数量为而不是在大多数语言中有限。例如，在大多数语言中有无数个形式为return foo + bar + ... + baz;的陈述。

A.是否有可能通过n个语句来证明产生x（也许是通过s）的程序P，在m语句中没有Q可以找到（以有效的方式）？

（我假设你忘了m < n这里，否则这个问题就没有意义了。）

不，它不能在所有的证明。

B.可以找到最小n（有效的方式）吗？

不，根本找不到。

C.最小n保证是1吗？

正如我在开始时所说的，它取决于语言和上述问题的目的，我假设一种语言，其中的答案是否定的。