SIGBOVIK 2007:广义超级马里奥兄弟是 NP 完全的
SIGBOVIK 2007: Generalized Super Mario Bros. is NP-Complete
频道:suckerpinch · 时长:4:22 · 发布:2008-05-11 · 播放:83675
简介
Tom Murphy 在 SIGBOVIK 2007 的讽刺演讲,以笔名发表,证明广义超级马里奥兄弟是 NP 完全的。这是对复杂性理论结果的一个简短、冷面幽默的演绎。
HN 为什么推荐
HN 喜欢它作为一个有趣、娱乐性的演讲,经常在关于游戏 NP 难度和 NES 自动化的讨论中被链接。
这家伙是个天才,而且超级搞笑 — HN, 2018
中文字幕节选
大家好,我叫Vargo Max V Vargo Max,我的论文是《广义超级马里奥兄弟是NP 完全问题》。很抱歉我没能来SIGBOVIK,我被卡住了,让我告诉 大家,我的工作是关于超级马里奥脸和马,许多胡子花了大笔经费 把游戏归类到复杂度类,比如俄罗斯方块是NP,国际象棋 是PSPACE等等。然而许多1985年日本的著名游戏被 弃之不顾,这是一种类别歧视。在本文中,我 要展示1984年的游戏《超级马里奥兄弟》,讲的是两个兄弟 落入梦幻世界,证明NP完全。砖块上的跳跳人,现在我要告诉你们 《超级马里奥兄弟》是任天堂公司为家庭电脑8位机 制作的。超级马里奥兄弟是两个水管工,叫路易吉和马里奥。这里有一张 马里奥的图片,因为超级马里奥兄弟在8位家庭电脑上,屏幕 限制为32×32块砖来显示,它处于复杂度类,不可能完成 第一步是将其广义化,我们说现在梦幻世界的大小是无穷大乘以 无穷大块砖,这意味着马里奥可以有一个非常大的房子或城堡 为了证明广义大小的超级马里奥兄弟不可能完成 有两个步骤,每个F步骤一个。第一步证明如果你能解决马里奥 那你就能解决图着色。第二步,8位可靠性,证明如果你能 给图着色,那么马里奥就能打败库巴,龟壳人之王 第一步,在无穷大乘以无穷大的广义梦幻世界中,马里奥有一个非常 大的城堡,地址是水管工城1715号,他和他的兄弟 路易吉住在这里。现在假设不失一般性,一个想要被 着色的图,你能给这个图着色吗?要着色,马里奥首先需要去 油漆店,位于油漆店大道4101号,城市,去获取许多颜色,用于马里奥绘画,但 家庭电脑只有9或10种颜色,所以马里奥踏上了征途,他 非常非常饿,因为没有足够的水管工工作,所以马里奥的征途是为了吃 和美元。这就拼出了QED,所以我们完成了。在 最后一部分,我展示了广义超级马里奥兄弟不可能太难。现在来展示 它不是多项式的是下一步。这很简单,我们只需要 看看单词polynomial的派生,polynomial意思是许多名字,因为poly是 拉丁语中的鹦鹉,鹦鹉的名字,而nomial意思是许多,像这个演讲有 名义数量的幻灯片,而马里奥只有一个名字,没有姓,比如马里奥·斯威夫特 或马里奥·琼斯,也没有名,比如JJ Jingleheimer Mario Luigi Smith MCX LV II B A BSC M MSC MBA DDS P hdjd,然后对他来说,他在 不是多项式的。实际上有些人不验证这个证明,在SIGBOVIK上,因为 非构造性等等。我给出了另一个证明,马里奥在 马里奥油漆店大道得到的所有油漆,他可以涂在图上给它着色,请看这张图片 看,你给它着色了 QED。未来工作,在职业安全研究社区,他们想留下微小的 面包屑问题轨迹,这样York就能继续从美国机构获得资助,所以 在这部分,我告诉你们未来的问题。问题一:当马里奥 跳上旗杆时,为什么天空会爆炸?问题二:为什么兄弟俩不想
HN 上的讨论
这家伙是个天才,而且他妈的还特别搞笑,我就知道我认得他的声音;看看这个:[VIDEO] — hotwire, 2018-06
既然我们在分享 Tom Murphy 关于马里奥的精彩作品,我必须附上他视频“广义超级马里奥兄弟是 NP 完全问题”的链接:[VIDEO] — dane-pgp, 2021-11
每当我看到这样的论文,我都会想起 Vargomax V. Vargomax 那篇经典的 SIGBOVIK 2007 论文[1]。那个演示也很有趣[2]。[1] [LINK] [2] [VIDEO] — groovy2shoes, 2013-05
类似的例子:[LINK] [LINK] [LINK] [LINK] [LINK] [VIDEO] [LINK] [LINK] [LINK] [LINK] [LINK](通过遍历 HN 上关于图灵完备和 NP 完备的搜索结果生成) — ikeboy, 2016-05
相关视频
- QuakeCon 2012 - John Carmack 主题演讲 · QuakeCon Official · 3:36:38
- 技术演讲:Linus Torvalds 谈 git · Google · 1:10:15
- QuakeCon 2011 - John Carmack 主题演讲 · QuakeCon Official · 1:26:38
- John Carmack Facebook Connect 2021 主题演讲 · UploadVR · 1:01:32
- Ruby Conf 12 - Y Not- 函数式编程历险记 by Jim Weirich · Confreaks · 53:21
- USENIX Security '18-Q:为什么主题演讲者不断建议改进安全性是可能的? · USENIX · 51:22
- 爱的陷阱 · Ben Woodhams · 2:58
- 28c3:不安全性的科学 · 28c3 · 59:23
- Philip Wadler 的“命题即类型” · Strange Loop Conference · 42:43
- Break Me00 The MoVfuscator 将mov变成令人崩溃的逆向工程噩梦 Christopher Domas · Adrian Crenshaw · 46:19
- NaN 门和翻转 FLOPS · suckerpinch · 19:07
- 数学的根本缺陷 · Veritasium · 33:59
- Erlang电影II:续集 · gar1t · 9:55
- 论PowerPoint的图灵完备性(SIGBOVIK) · Tom Wildenhain · 5:33
- 鸡鸡鸡鸡 · Yoram Bauman · 4:06
- 生命中的生命 · Phillip Bradbury · 1:30