论文标题
“扩展解决方案集的基础性”标准，用于建立NP问题的棘手性
The "cardinality of extended solution set" criterion for establishing the intractability of NP problems
论文作者
论文摘要
任何问题的棘手性及其解决方案的随机性具有明显的直观联系。但是，到目前为止，挑战是没有实际的方法可以牢固确定解决问题的解决方案是否实际上是随机的（或者它是否具有某些隐藏的未发现的结构，而该结构在被检测到后会使它变得非随机化）。这阻止了严重问题的结论性声明（例如NP）绝对是棘手的。为了解决这个问题，开发了一个称为“可扩展性”的概念。基于此，被称为“扩展解集的基数”的标准被认为是为了确定任何序列的（非）随机性。此外，这可以用来根据其解决方案是随机还是非随机来确定任何问题的（在）障碍性。该标准应用于诸如2-SAT，3-SAT和近似硬度之类的问题，以分析其（在）障碍性。最后，还提供了基于相同标准的唯一游戏猜想的有效性的证明。
The intractability of any problem and the randomness of its solutions have an obvious intuitive connection. However, the challenge till now has been that there is no practical way to firmly establish if the solution to a problem is actually random (or whether it has some hidden undiscovered structure, which upon being detected would render it non-random). This has prevented the conclusive declaration of hard problems (such as NP) as being definitely intractable. For dealing with this, a concept called "extensibility" of a sequence is developed. Based on this, a criterion termed as "cardinality of extended solution set" is conceived to ascertain the (non)randomness of any sequence. Further, this can then be used to establish the (in)tractability of any problem depending on whether its solutions are random or non-random. This criterion is applied to problems such as 2-SAT, 3-SAT and hardness of approximation to analyze their (in)tractability. Finally, a proof for the validity of the Unique Games Conjecture based on the same criterion is also presented.
