来写点跟这些玩意有关的东西好了 (这些是属於计算机理论的东西 是近几十年才出现的理论 咱们资工系在研究的东西就是从这里堆上来的 (远目)) ------------------------------------------------------------------------- 什麽是 P vs NP 问题？ 这里是数学版就讲一点数学上的定义好了 P 跟 NP 都是所谓的「复杂度类」(Complexity class) 它们都是集合 集合的成员是许多的「问题」 这些问题都是所谓的「是非题」 例如 「给定一张地图 问有没有一条路径恰好走过每条路一次」 像这样子的问题 (如果像是「给定一张地图 问恰好走过每个点一次的最短路径有多长？」 这种问「量」的问题则可以藉由增加一个量的参数把它转化成像是 「给定一张地图和 K 值 问有没有一条恰好走过每个点一次的路径比 K 短？」 这样的是非题 然後重覆询问这个是非题去得到所求的量的答案 因此也可以使用这种分类法) 这种问题都会有一或数个可变动的参数 表示题目的大小 例如上面那个问题参数可能包含「交会点的数目」或「路的数目」等等 一般来说 这个参数越大要解开题目所花的时间就会越多 有的题目 即使参数变成十倍 时间只要多一下下就好 有的题目 它的参数变成两倍 时间就要两倍 有的题目 即使参数只多个一 时间就要两倍 那分类这些题目的方式就是使用这种「复杂度类别」 上面说的是对时间分类 所以称做「时间复杂度」 这是最常见的一种分类法 当然要谈计算时间就要说明是在什麽样子的计算模型下计算 也就是说要说明「到底做什麽事会花多少时间」 基本上常用的是所谓「确定型图灵机」(Deterministic Turing Machine) 这东西只要大概想像成和咱们现在的电脑差不多就行了 因为这东西如果要细说它的数学定义那就又要一篇了 XD (不知道各位记不记得今年 6/23 这个 Google doodle: http://www.google.com/doodles/alan-turings-100th-birthday 这玩意就是一个确定型图灵机 这是 Google 纪念这套计算机理论的建基者 Alan Turing 的一百岁生日做的) 回到原来的问题 刚刚说 P 跟 NP 是复杂度类 它们是属於刚才提到的对时间分类的复杂度 P 是表示「解决问题所需要的时间至多是参数的多项式函数」 也就是说 顶多是参数两倍的话时间变八倍或十六倍这种程度而已 (计算机理论里通常简称这样的时间花费叫做「多项式时间」 因为这个叙述太常用了但每次都这样讲会很拗口...) 而 NP 则是表示「给定问题和一个声称的答案 要检查这个声称的答案是不是真是答案 需要多项式时间」 虽然听起来好像差不了多少 但很多时候我们知道一些题目求解跟证明它是解差很多 例如质因数分解 给一个几百位的数求分解会死人 但是如果是给一个几百位的数和一个声称是它的质因数分解的答案 那我们只要先检查这声称的答案里的数字是不是真是质数 然後再把它乘起来看看就可以确定了 像这样的问题就会在 NP 里 P vs NP 问题就是问说这样子的两个集合到底是不是同一个 之所以会这麽问是因为 NP 里面有些问题如果要去解它所需要的时间通常会是参数的指数函数以上 这代表参数只要加一 时间就要变成几倍 但现在却不知道这些问题有或没有需要多项式时间的解法 (不知道是真的不知道喔 也就是目前没有证明也没有反证) (顺带一提 并不是所有需要时间至多是指数函数的问题都在 NP 喔 有另一个时间复杂度类叫 EXPTIME 的才是指这种问题 而其实上几行的指数函数也不怎麽对 因为现在有些问题目前已知需要的时间 没有到指数函数那麽扯但又没有多项式函数那麽和蔼可亲) 这些问题的一部份特别被叫做 NP-Complete (NP完全) 它收集的问题具有下面这个性质 「它属於 NP，而且其他任何一个属於 NP 问题都可以花费多项式时间转换成这个问题」 它对 P vs NP 问题的贡献就在於 只要一个 NP-Complete 问题被证明能够以多项式时间解决 那麽根据这个性质 所有的 NP 问题就都能以多项式时间解决 於是就证明了 P = NP 反过来 只要一个 NP-Complete 问题被证明不能够以多项式时间解决 那麽因为这个问题属於 NP 但却不属於 P 所以 P≠NP 无论哪一个都是解决了 P vs NP 问题 (附带一笔一百万镁的奖金) 不过 「NP-Complete」这个概念自从 1971 年被提出来之後 现在已知有至少三千个问题是属於 NP-Complete 的 但是四十年来没有人能对其中即使任何一个给出多项式时间的解法或证明不存在 甚至连两年前号称证明了 P≠NP 的那位 Vinay Deolalikar 他的证明 也被其他专家找出了几个重大错误 这个问题才被称为是世纪难题之一 另外要讲的一个常见误解是: NP (或 NP-Complete) 表示「无解」 这是错的 (而且大概十有八九是被 NP 的 N 字给误导了) 它只是不知道有没有「很快的解法」而已 因为总是有一个「解法」叫做「暴力测试」 就是把所有可能答案都扔进去试一试 只是所有的可能答案个数是参数的指数函数 要暴力来的话很慢而已 ------------------------------------------------------------------------- 那，它跟踩地雷有什麽关系？ 总算回到原 PO 一开始的问题了 这位 Richard Kaye 教授他在 2000 年时 在 Mathematical Intelligencer 这个杂志上投稿了一篇文章 这篇文章证明了下面这个「踩地雷问题」是 NP-Complete: 「给定一个盘面，包含一些已经打开的数字和可能会有的一些已经标记的地雷， 是否存在一个地雷分布使得这个盘面能够出现？」 在 NP-Complete 问题已经被研究了这麽久的现在 要证明一个问题属於 NP-Complete 通常是用这个方法: 去找另一个 NP-Complete 问题 然後试着用多项式时间把那个问题变成这个问题 根据上面提到的 NP-Complete 问题的性质 这样就证明了这个问题是 NP-Complete (转不过来的话再仔细想一想 XD) 这篇文章所选用的另一个问题是所谓的「可满足性问题」: 「给定一个逻辑式子 (也就是由 And/Or/Not/什麽有的没的连接的式子)， 是否能够将式子中的变数取定 True 或 False 使得整条式子得到 True？」 这个问题是当年 NP-Complete 这个概念被提出来时 所证明的第一个属於 NP-Complete 的问题 (当然因为是第一个所以不能使用上面这个方法 所以是直接证明「可满足性问题」具有 NP-Complete 的性质 这个如果要写又要一篇了 XD) 而 Kaye 教授所使用的把这个问题变成踩地雷问题的方法是..... 直接在踩地雷的盘面上画逻辑电路图！ http://web.mat.bham.ac.uk/R.W.Kaye/minesw/minesw.pdf 这个是 Kaye 教授放在他的个人网站上的 pdf 档 (http://web.mat.bham.ac.uk/R.W.Kaye/minesw/ 原始来源) 里面展示了一些他在那篇文章里所用到的「电路图元件」 例如「电线」、「Not 闸」、「Xor 闸」、「And 闸」等等 利用这些「元件」就能够在踩地雷盘面上拼出一个逻辑电路图出来 也就是说 「一个逻辑电路能不能成立」转变成了「一个踩地雷盘面有没有解」 这样就证明了这个「踩地雷问题」是 NP-Complete 了 原 PO 你的问题看了这里列的这些「元件」大概多少能够有一点感觉吧？ ------------------------------------------------------------------------- 可是这个证明用的是自己设定的地雷吧？这样的话那那些随机的怎麽办？ 这个问题有点误解了这个证明 这个证明是在说 「现在我用踩地雷盘面画了这个电路图 如果有哪个家伙有办法对所有踩地雷盘面都可以快速解 那我这个盘面也要能解 而这个盘面的解可以变成可满足性问题的答案」 也就是说 他其实不是在证明他找到了快速方法 反而是证明了几乎不太可能找得到快速方法来解 (不然我们就证明了 P = NP 了) ------------------------------------------------------------------------- 总觉得这个「踩地雷问题」跟平常的踩地雷还是没什麽关系... 当然有关系啊 XD 当我们想测试某个格子是不是地雷时 就把现在的盘面复制一份 把那个格子标上旗子 然後丢给这个问题的解决方法 如果它说这是不可能的那这一格就绝对安全 同样的 如果那一格标上 0 ~ 8 再丢给这个问题去解都说不可能的话 那这一格就可以标旗子了 这正是一个解平常的踩地雷的演算法 XD (虽然慢透了就是) (不过通常的踩地雷是还有另一个线索叫做「剩余地雷数」 有的时候这是可以做为推理的材料的 这个演算法并不使用这个线索 也就是说它并没有特别限制剩余地雷数) ------------------------------------------------------------------------- 好吧，那这个教授为什麽会想到要去证明这个？ 根据他自己的说法 是因为有的时候我们必须得要看过整个盘面才能确定下一步要怎麽做 ┌────────┐ 像是左边这个他举的例子 ＊是已经标出来的地雷 │２３＊２２＊２１│ │＊＊５　　４＊２│ 要确定？那一格安不安全 │　？＊＊＊　４＊│ │＊６　６＊＊　２│ 非得把几乎所有还没开的格子都检查过一遍 │２＊＊　５５　２│ │１３４　＊＊４＊│ 还要做几个假设才可以导出那一格是安全的 │０１＊４　　＊３│ │０１２＊２３＊２│ 这跟 NP-Complete 问题的那种「暴力解法」有种相似的感觉 └────────┘ 所以才会去试着证明它属於 NP-Complete ------------------------------------------------------------------------- 嗯，踩地雷的部份了解了，那密码学又是怎麽一回事？ 这个其实是只要提到 NP-Complete 或 P vs NP 问题时 99% 会举的例子 那就是 RSA 公开金钥加密演算法 因为这是实际上有着广泛应用的东西 而又能够跟 P vs NP 问题扯上关系 比较能够有「这似乎是这个理论的实际应用」的感觉 (虽然实际上大概不会是 :P) 细节不多说 重点在於 RSA 的加密安全性是建立在 「将一个几百位的大数字做质因数分解目前没有快速的方法」这个事实上 (尤其要注意的是 「质因数分解」这个问题只已知属於 NP 是不是属於 NP-Complete 都还不知道) 但是如果 P = NP 被证明的话 那麽属於 NP 的质因数分解就会存在一个多项式时间的做法 这样一来 RSA 的安全性就会崩溃 ------------------------------------------------------------------------- 一个题外话 其实 RSA 不需要到 P = NP 才会崩溃 因为早在 1994 年就有一个叫做 Peter Shor 的家伙 给出了一个在「量子电脑」上用多项式时间做质因数分解的演算法 这就是上面提到的「计算模型」的不同 平常没有明说的时候都是使用「确定型图灵机」这个计算模型 因为它最接近我们目前使用的电脑的计算模型 NP 其实有另一个使用「非确定型图灵机」的计算模型的定义 (NP 的 N 字其实就是指这个「非确定型图灵机」 而不是什麽「非P」的) 这里则是「量子电脑」这个计算模型 所以当年 IBM 的那些人号称实作了这个演算法时可想而知有多轰动 XD ------------------------------------------------------------------------- 目前能讲的就这些了 这些计算机理论的东西要讲深下去就等於是咱们资工系的一门课了 那可不是这里几篇文章就可以讲得完的东西 (远目) ------------------------------------------------------------------------- Reference: * Richard Kaye 教授的网站; 这是关於踩地雷的部份 http://web.mat.bham.ac.uk/R.W.Kaye/minesw/ * 由某未知来源找到的该篇杂志文章 :P * 维基百科的许多条目 * 本人的修课记忆 XD -- 'Oh, Harry, don't you see?' Hermione breathed. 'If she could have done one thing to make absolutely sure that every single person in this school will read your interview, it was banning it!' ---'Harry Potter and the order of the phoenix', P513 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 180.218.108.125 (删除广告推文) ※ 编辑: LPH66 (123.195.194.100 台湾), 05/26/2020 17:41:03