In this paper we critique Keum-Bae Cho's proof that $\mathrm{P} \subsetneq \mathrm{NP}$. This proof relates instances of 3-SAT to indistinguishable binomial decision trees and claims that no polynomial-time algorithm can solve 3-SAT instances represented by these trees. We argue that their proof fails to justify a crucial step, and so the proof does not establish that $\mathrm{P} \subsetneq \mathrm{NP}$.
翻译:在本文中,我们批评了Keum-Bae Cho关于$\ mathrm{P}\ subsetneq\ mathrm{NP}$的证明。 这个证明将3SAT事件与无法区分的二元决定树联系起来, 并声称没有多元时算法可以解决由这些树代表的3SAT事件。 我们争辩说,它们的证据不能证明一个关键步骤是合理的, 所以证据不能证明$\ mathrm{P}\ subsetneq\ mathrm{NP}$ 。