最小陳述數量：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嗎？

正如我在開始時所說的，它取決於語言和上述問題的目的，我假設一種語言，其中的答案是否定的。