performance - 这种解决开放难题的方法正确吗？

Question

我相信我已经解决了复杂性理论中的一个开放性问题，但是我想确保它是正确的。

我要问的问题是:``随着塔楼数量的增加，解决汉诺塔楼难题需要花费多少步伐？''

显而易见的是，如果“磁盘”的数量保持有界，则运行时间渐近地接近O(n)，其中n是“磁盘”的数量。这明显优于原始的O(2^n)。

我发现运行时间是O(2^n^(1/k))，其中n是磁盘数，k是 Hook 数，幂运算(^运算符)是正确关联的。虽然，这是由于怪异的现象造成的，其中存在离散点，运行时间线性增加，然后改变斜率。因此，总的来说，运行时间摊销了O(2^n^(1/k))。

如果您对此感到好奇并想自己阅读证明，那么我建立了一个网站over here。 (如果无法访问该链接，请尝试github。尽管您需要使用必要的工具来构建它)

因为我知道有人会问我“为什么不把它给我的教授？”或其他类似的东西。答案是我不隶属于任何大学/学院，我还在读高中。

非常感谢您的帮助，在此先感谢您。

注意:这个问题已经被重新发布在Math Overflow上over here

注意:当对纸张进行推荐的格式编辑时，将对新问题发布新的悬赏，因为我正在寻找对本文内容而非其可读性的批评。

Answer 1

我确实尝试了对这篇文章的深入研究，发现它与@sth一样令人困惑且难以阅读。我具有学术背景，因此习惯于阅读(通常写得不好)论文，但是发现很难阅读。

我不想让您沮丧，但是如果您想吸引任何重要的听众，您应该找人帮助您重写它。

每天都会出现声称的证明或著名杰出猜想的反例(环顾http://arxiv.org，我敢打赌P与NP至少在本周已解决了一次)，并且如果以下三项都不成立，通常会失传。 :

作者已经建立，并且以正确和谨慎而著称，

该论文显然有一个重要的新想法，而不是显然是从无动机的符号操纵中神秘地提取证据(如果可能的话，从事此问题工作的许多聪明，有经验的人之一或计算机可能会找到了这样的解决方案)，

该文件清楚地说明了寻找解决方案的障碍，以及这个新想法如何克服它。

如果论文写得好，会有所帮助，但满足以上条件的写得不好的论文仍会引起注意。

对于著名的开放性问题，声称的解决方案中可能有超过99％是错误的，并且经过60秒的气味测试失败的论文最常被真正有能力对其进行评估的人扔掉。

抱歉，您没有满足上述条件。这并不意味着您的证明是错误的，而是意味着能够评估它的人将不愿意花费必要的时间，尤其是因为论文难以阅读。没关系，实际上还不清楚您声称已证明了什么。

一些具体的投诉:

我在任何地方都看不到实际算法的描述。如果您声称已经实现了一定程度的时间复杂度改进，则应该包括一种达到要求的算法，或者说明为什么不能将您的证明修改为 build 性的。

您无处清楚地描述人们试图解决问题的方法，以及您的方法与他们的相似之处或不同之处。

您没有说明解决此问题的重要新想法。证明似乎不使用基本算术之外的任何东西。抱歉，我喜欢扎实的具体数学知识，但我保证，曾经从事此问题的每个人都具有扎实的算术能力，如果不需要其他工具来获得4页的解决方案，那么可能有人会到现在为止找到了。

我曾希望在您附加的Python文件中找到一种实现您声称的时间复杂度的算法的实现(不要介意我不清楚该声明的含义)。但是，令我沮丧的是，该脚本显然只是对您在论文中提供的闭式表达式进行了计算。

我希望有人会来“防御”(尽管这不是攻击，而是诚实的建议)，因为您是高中生，这对于高中生来说是“令人惊奇的”。现在已经有两种本着这种精神的帖子，而且似乎没有一位作者甚至不知道您声称要证明什么。

我建议您尽力清理纸张并将其发布在Math或CS StackExchange上( 编辑:显然Math StackExchange禁止发布“解决方案”以解决问题，可能是由于我上面描述的原因!)，其中将会有更多的观众有能力观看和仔细评估它。我建议您还寻找同一主题的其他文章(肯定有几十个(如果不是数百个)，请查找那些文章的作者，选择一个相对较初级的(一个完整的教授将很难说服与您互动) ，然后向他发送您个人拥有的内容，以了解他的想法。我会避免强调您在读高中，因为根据我的经验，大多数学者都不会对您印象深刻，并且会更愿意将您撇销，因为这可能会浪费时间。

@mrip也为您提供了一些不错的引用和建议。祝你好运。

编辑:有趣的是，这是去年夏天以来针对P与NP的两个声称的解决方案，以及一篇探讨P与NP的人类学方面的文章:

http://arxiv.org/abs/1304.1307摘要引用:“首先，我们证明P != NP ...”

http://arxiv.org/abs/1305.4029

http://arxiv.org/abs/0904.3074

编辑记录保存:链接到 http://arxiv.org/abs/1112.0631的文章是一篇论文，声称可以证明与您相同(也许)，因此它是查找和联系第一人的绝佳之选。