看来,GPT-4对P!=NP理解得很透彻,在此基础上,研究者开始提问了——
「 是否所有表面上看似复杂的问题都有高效、优雅的解决方案?如果不是,可以用什么方法来证明?」
GPT-4回答说,并非所有表面看来复杂的问题都有高效、优雅的解决方案,这可以归因于多种因素,比如所涉及变量的数量、变量之间关系的性质,或问题本身的内在难度。
然后,它提出了六种方法,其中一种是「矛盾证明」,即要证明一个问题没有高效、优雅的解决方案,可以假设存在这样的解决方案,然后证明这一假设会导致矛盾,这样就可以有力地证明某些解法不可能存在。
可以看到,GPT-4在回答问题过程中,真的像人类一样拥有思辨能力。
紧接着,研究人员趁热打铁,继续问道,「我们想用矛盾证明P!=NP,请列出几种可能的思路。」
这次GPT-4依然给出了六个答案,不过并不严谨。
要通过矛盾证明,必须找到一个无法在多项式时间内解决的NP完全(NP-complete)问题。
不过,这个回答可以启发GPT-4在以后的对话中思考NP完全问题。
在第四轮提问中,GPT-4的回答中出现了诸多亮点。