5

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

我的问题是:“随着塔的数量增加,解决河内塔谜题需要多少步?”

显而易见的是,如果“磁盘”的数量保持有界,那么运行时间会渐近接近O(n),其中 n 是“磁盘”的数量。这比原来的要好很多O(2^n)

我发现运行时间是磁盘O(2^n^(1/k))的数量,钉子的数量,取幂(运算符)是右关联的。虽然,这是因为一个奇怪的现象,其中存在运行时间线性增加然后改变斜率的离散点。所以总而言之,运行时间摊销了。nk^ O(2^n^(1/k))

如果您对此感到好奇并想自己阅读证明,我建立了一个网站,您可以在此处找到它。(如果该链接无法访问,请尝试github。尽管您需要访问必要的工具来构建它)

因为我知道有人会问我“我为什么不把它交给我的教授?”或者类似的其他问题。答案是我不隶属于任何大学/学院,我还在上高中。

任何帮助都非常感谢,在此先感谢您。

注意:此问题已在此处的 Math Overflow 上重新发布

注意:当对论文进行推荐的格式编辑时,将针对将发布的新问题发布另一个赏金,因为我正在寻找对论文内容而不是易读性的批评。

4

7 回答 7

6

我确实尝试过深入阅读这篇文章,但发现它非常混乱且难以以与@sth 相同的方式阅读。我有学术背景,所以习惯于阅读(通常写得不好)论文,但发现这一篇很难读完。

我不想让你灰心丧气,但如果你想吸引任何重要的观众,你应该找人帮你重写它。

著名的杰出猜想的声称证明或反例每天都会出现(看看http://arxiv.org,我敢打赌,P 与 NP 本周至少解决了一次),如果这三个猜想都出现,通常会失信以下事情不成立:

  • 作者已经站稳脚跟,以正确和谨慎着称,
  • 这篇论文显然有一个重要的、新的想法,而不是显然神秘地从无动机的符号操纵中提取证据(如果可能的话,许多聪明、有经验的人中的一个可能会发现这样的解决方案),
  • 该论文清楚地解释了寻找解决方案的障碍,以及这个新想法如何克服它。
  • 如果论文写得好,它会有所帮助,但是满足上述条件的写得不好的论文仍然会引起一些关注。

可能超过 99% 的著名开放性问题的解决方案都是错误的,而未能通过 60 秒气味测试的论文通常会被实际上有能力评估它们的人扔掉。

很抱歉,您不符合上述条件。这并不意味着你的证明是错误的,但它确实意味着能够评估它的人将不愿意花费必要的时间,特别是因为这篇论文很难阅读。没关系,实际上并不清楚您声称已经证明了什么。

一些具体的投诉:

  • 我在任何地方都没有看到对实际算法的描述。如果你声称已经实现了一定的时间复杂度改进,你应该包括一个实现它的算法,或者解释为什么你的证明不能被调整为具有建设性的。
  • 你没有清楚地描述人们试图解决问题的方法,以及你的方法与他们的方法有何相似或不同。
  • 你没有陈述你解决这个问题的重要新想法。除了基本的算术,这个证明似乎没有使用任何东西。抱歉,我喜欢脚踏实地的具体数学,但我保证曾经研究过这个问题的每个人都具有扎实的算术能力,如果不需要其他工具来获得 4 页的解决方案,那么可能有人会现在找到了。
  • 我曾希望在您附加的 Python 文件中找到一种实现您声称的时间复杂度的算法(别介意我不清楚声称是什么)。然而,令我沮丧的是,该脚本显然只是运行您在论文中提供的封闭式表达式的计算。

我希望有些人会为你“辩护”(尽管这不是攻击,而是诚实的建议),因为你是一名高中生,这对高中生来说是“惊人的”。现在已经有两个帖子本着这种精神,而且两位作者似乎都不知道你声称要证明什么。

我建议您尽可能地清理论文并将其发布在 Math 或 CS StackExchange 上(编辑:显然,Math StackExchange 禁止发布未解决问题的“解决方案”,这可能是因为我上面描述的原因!),在那里会有更多的观众能够仔细查看和评估它。我建议你也寻找同一主题的其他文章(如果不是数百,肯定有几十个),查找这些文章的作者,选择一个相对初级的(一个正教授会更难说服与你互动) ,然后把你个人拥有的东西发给他,看看他是怎么想的。我会避免强调您在高中,因为根据我的经验,大多数学者不会留下深刻印象,并且会更愿意将您注销,因为这可能是浪费时间。

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

编辑:只是为了好玩,这是去年夏天 P 与 NP 的两个声称的解决方案,以及一篇探讨 P 与 NP 的人类学方面的文章:

编辑以保存记录:链接在http://arxiv.org/abs/1112.0631的文章是一篇声称可以证明与您相同的事情(也许)的论文,因此这是一个很好的第一个查看位置和第一个联系的人。

于 2013-12-29T02:22:16.740 回答
1

这对一个高中生来说是很棒的工作。保持。我还没有完全阅读你的文章,但这里有一些一般性评论。

由于这个问题有两个参数,所以在使用渐近大 O 表示法时,您需要小心地准确指定您的意思。例如,如果 n 保持有界,则 O(n) 与 O(1) 相同,因为此时 n 只是一个常数。此外,如果中间 peg 的数量大于磁盘的数量,那么在 2n 步内很容易解决问题,因为您只需将每个磁盘移动到它自己的中间 peg 上。

如果您要导出一个对 n 和 k 的任意值都有效的界限,那么您的公式应该同时包含 n 和 k。否则,您应该指定挂钩数与您的绑定有效的磁盘数之间的关系。

我建议检查您的结果,并与互联网上有关河内多钉塔问题的一些可用论文进行比较。例如,对于常数 k,本文推导出 2^(C_k n^(1/(k-2)) 形式的下界,其中 n 是磁盘数,k 是钉子数,C_k 是取决于 k 的常数,在给定现有算法上限的情况下,这表明问题的复杂度为 2^Θ(n^(1/(k-2))。

http://www.cs.rutgers.edu/~szegedy/PUBLICATIONS/tower1.pdf

这是另一篇论文,它考虑了钉子数量随磁盘数量而增长的情况。

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.36.7500&rep=rep1&type=pdf

如果您再google一下,您可能会发现更多关于这个问题的已知和未知的信息。就写作而言,我建议您在进行证明之前在顶部清楚地说明您的主要结果。

于 2013-12-29T01:57:24.293 回答
1

我没有深入研究它,但有一些我发现令人困惑的事情:

  • 在 (1) 中有一个变量g和相关变量g b,但没有解释这些变量应该是什么。
  • (1)的内容需要证明吗?例如,在最后一种情况下,前面的文字似乎没有解释2 b 。我认为应该在某处解释/证明其正确性。
  • (1) 之后的“k=2 的证明”似乎不能证明 (1),而是从中推导出更多的东西。目前尚不清楚该证明到底要证明什么,您可能应该在它之前添加一个引理/定理,说明将要证明的内容。
  • 同样,“一般证明”也没有明确说明它试图证明什么。
于 2013-12-29T01:18:43.713 回答
0

这对于一个高中生来说是非常非常高的水平。您应该将此作为简历发送到谷歌或其他地方工作。甚至 TeX 的使用也令人印象深刻。

我认为问题在于您没有考虑第三条规则,即大磁盘不能放在较小的磁盘上。

取自本网站:http ://www.cut-the-knot.org/recurrence/hanoi.shtml

上面的递归解决方案涉及将两次 (N - 1) 个磁盘从一个钉子移动到另一个钉子,并在其间再移动一次。然后它遵循

TN ≤ TN-1 + 1 + TN-1 = 2TN-1 + 1

对这个问题的传统解释是明确定义的,并指出我们不能简单地将塔倒置在另一个钉子上,而以正确的方式在另一个钉子上重建。主要是因为它违反了在小磁盘上没有大磁盘的规则。

基本上解决它的最快方法是每个磁盘至少移动两次。

不幸的是,加法的交换性不会对磁盘​​集强制执行任何排序约束,因此大磁盘可以放在小磁盘之上。

话虽如此,我只是一名软件工程师,而且我已经有几年没有做过 comp-sci 或数学了。所以你应该得到第二个意见。

你已经在一个网站上设置了这个,让你的论文受版权保护,也许还可以通过电子邮件向计算机科学教授发送指向你网站的链接。

此外,如果您不知道您可能对这个计算机科学领域感兴趣:http ://en.wikipedia.org/wiki/List_of_unsolved_problems_in_computer_science

不要对我在这里说的任何话感到灰心,你比我在高中的时候早了几光年,我相信你会在学术界有所作为。向您的网站发送链接,寻求反馈并不断寻找提高您对数学理解的方法。

另外,请查看 topcoder.com - 那里有一个您可能也会感兴趣的算法部分。他们的论坛也可能会提供比我更好的反馈。

于 2013-11-14T06:54:45.940 回答
0

请注意,有一种迭代方法可以解决河内塔。如果您还没有这样做,您可能想检查是否可以说服它产生相同的结果。

于 2013-12-28T23:00:12.963 回答
0

编辑:没关系所有这些:

这里有问题,我无法完全理解你到底在想什么,所以我会继续阅读。基本上,我的疑虑是,在 Mk(n) 的第二个等式中,您的递归解决方案只考虑 Mk-1(其他一些 n)。

这可能是因为您不建议具体排序,而只建议运行时( Mk(n) )。理想情况下,您会指定一些排序,然后基于将您的排序映射到运行时的函数进行争论。在字里行间阅读,您的“排序”总是形式为将 i 盘移动到 A,将 n - i 盘移动到 B,将 i 盘从 A 移动到 B。这正是原始问题的解决方案 (M2(n) )。然而你声称更快的运行时间?

考虑案例 M3(3) 的明显解决方案。一个人只需将圆盘展开,分 5 步解决。您的“扩展总和”提供了最佳的 7 步解决方案。我不认为这是您逻辑中的错误,但这是您的阐述中最明显的错误。请详细说明 Mk(n) = Mk-1(i) + 2Mk(ni) 的含义。据我了解,这意味着您通过首先移动 i 个圆盘,然后是 n - i 个 dsics,然后再移动 i 个圆盘来解决 Mk(n)(递归 - 这当然是合法的)。问题以这种方式扩大当然并不代表任何合法的解决方案。很明显,这并不完全是您脑海中的顺序。您脑海中的顺序涉及递归中一系列递减的 k 值。

查看 M4(4) 以了解差异。您用 Mk-1 显示的展开式给出了与 M2(n) 类似的解。现在考虑您想要编写的解决方案,将它们展开。在前两个圆盘被移动之后,接下来的圆盘就更少了。具体来说,他们的运动是 M2(2) 问题的一个例子。仔细阅读。2 . 不是 k-1 = 3。

于 2013-12-29T03:36:27.760 回答
-1
I problem in question is: ``How many moves does it take to solve the Towers of Hanoi puzzle as the number of towers increases?''

What I've found is that if the number of ''disks'' is kept bounded, then then running time asymptotically approaches O(n) where n is the number of ''disks''. This is significantly better than the original O(2^n).

这并不奇怪。如果圆盘的数量有界n,那么一旦有n开放的钉子,移动就有一个平凡的解决方案2n

悬而未决的问题大概是关于磁盘数量何时不受限制。对于给定数量的挂钩,随着磁盘数量的增加,解决方案大小会发生什么变化n。它像 一样呈指数增长(据我们所知)2^n,而不是 的线性函数n

于 2013-12-29T04:38:13.363 回答