如何解決3SAT使用蠻力和N.D.M

Question

我一直在研究和嘗試解決3SAT使用蠻力和N.D.M，但不能這樣做。任何人都可以向我詳細解釋這些，並告訴我使用蠻力和N.D.M解決3SAT的基本算法？謝謝

Answer 1

一個蠻力解決方案只是嘗試所有可能的輸入。因此，試圖解決（A | B）嘗試000,001,010,011,100,101,110,111其中xyz是A = x，B = y，C = z。

如果通過NDM您的意思是非確定性機器https://en.wikipedia.org/wiki/Non-deterministic_Turing_machine有不同的思考方式。一種是假設你必須爲計算時間付費，但是合同存在漏洞，如果你嘗試所有可能的投入，你只能爲這些嘗試中最長的運行收費 - 所有其他人都是免費的。