SCP-CN-2279 - 三染色问题的决定性多项式时间求解程序

[[module css]]
.page {
    display: block;
    overflow: hidden;
    font-family: "Monotype Corsiva", "Bradley Hand ITC", sans-serif;
    font-style: normal;

    background-attachment: scroll;
    background-clip: border-box;
    background-color: transparent;
    background-image: linear-gradient(to top ,rgb(202, 219, 228) 0%, rgb(231, 233, 220) 8%);
    background-origin: padding-box;
    background-position: 0px 8px;
    background-repeat: repeat;
    background-size: 100% 20px;

    border: 1px solid #CCC;
    border-radius: 10px;
    padding: 10px 10px;
    margin-bottom: 10px;

    box-shadow: 0px 1px 3px rgba(0, 0, 0, 0.2)
    }
.page p,
.page ul {
    line-height: 20px;
    margin: 0;
}
[[/module]]

[[>]]
[[module rate]]
[[/>]]
**项目编号：**SCP-CN-2279

**项目等级：**Safe

**特殊收容措施：**唯一一台载有SCP-CN-2279的计算机储存于Site-CN-01的Kempe有限计算处理中心，由中心主任Dr. Zhang与助理Dr. Lee进行维护。此台计算机应与中心内提供的局域互联网以及外部互联网物理隔离。如有部门希望借助SCP-CN-2279对其他项目的特殊收容措施进行初步规划，该部分负责人应遵循表格CN-2279中提供的信息，向Dr. Zhang提出符合规范的申请。

禁止向SCP-CN-2279提供没有完全遵循表格CN-2279规范的信息。禁止将SCP-CN-2279用于除规划特殊收容措施以外的其他待解决问题。禁止对SCP-CN-2279进行反编译。

**描述：**SCP-CN-2279是一异常程序，由基金会异常算法部门的研究员Leppa和Dr. Nekah共同开发完成。SCP-CN-2279的可接受的初步输入为一有限邻接矩阵[[$ M $]]，输出为以字符串形式表示的[[$ M $]]所对应的有限图[[$ G $]]的一种三染色。

鉴于判断任一有限图是否存在三染色这一问题是[[$ NP $]]-完全的，SCP-CN-2279曾被试图用于解决大量[[$ NP $]]-完全问题。尽管SCP-CN-2279在大部分情况下可以在较短时间内给出答案，但大多数情况可归为下列之一：
* 答案错误

* 答案正确，但载有SCP-CN-2279的计算机已将输入数据发送到所连接的局域网内所有终端进行运算，且所有终端进行死循环

* 输入问题不存在符合要求的答案，但在SCP-CN-2279输出答案后，输入问题在所有载体上更改条件使得输出答案为正确答案，可受影响的载体包括纸张、电子数据、记忆以及现实

* 输入问题存在符合要求的答案且SCP-CN-2279独立运行解得的答案为不更改任何条件下的正确答案，但SCP-CN-2279所在站点内会出现一例从未被计划收容的异常项目

由于SCP-CN-2279展现出的不可控性所带来的危害远超于其潜在益处，SCP-CN-2279长时间被禁止使用。在事故CN-2279-1后，研究员Nekah设计并完善了表格CN-2279，以协助各部门对异常项目的收容措施进行规划。

在使用SCP-CN-2279时，提交申请的部门应简要说明希望收容的项目的部分性质，列于表格CN-2279内的应特别注明。收到申请后，相关人员会根据所列出的性质以及表格CN-2279生成可能含有额外属性的有限图[[$ G $]]。将[[$ G $]]转化为对应[[$ M $]]输入SCP-CN-2279并运行后，答案所给出的染色方式亦可通过表格CN-2279转译为合理的初步收容措施，相关部门可以自行增添进一步的收容措施，或提供更多性质以便于再次运行SCP-CN-2279得到更优化的建议。

**附录CN-2279-2：**一次规范使用SCP-CN-2279协助收容的录音记录
> **<开始记录>**
> 
> **Dr. Zhang：**小子，模因部来了一份新的申请，把机子打开吧。
> 
> **Dr. Lee：**模因部，我看看……“传播性”，所以“有向”。“需大量人员分为不同用途”，“等分”。张叔，这个被划了的“五”啥意思？表格上没有啊。
> 
> **Dr. Zhang：**坏了，我这脑子也想不起来了。“五”……先把“不包含彼得森图”勾上，这条件我只记得他们申请的时候用得上。
> 
> **Dr. Lee：**每次都写这种模模糊糊的这不是添麻烦嘛。他们自己好多时候默认的东西也不写，都得我们一个一个检查。“非高维”，他们没特意说不是那就肯定是了，“平面”。“无需独立收容间”，“稀疏”。
> 
> **Dr. Zhang：**录着音呢，收着点。
> 
> **Dr. Lee：**这不是正好说给他们听，他们更熟悉了我们不就更方便了。“正则”，不用。“二部”，不用。
> 
> **Dr. Zhang：**那要是大家用表格都跟你一样熟练了，还要你这小子干啥？“临界”也不用，还没到那个级别，他们资源也够。
> 
> **Dr. Lee：**这都是您教我的，您又没教过别人，那我怕啥？您看眼，这些差不多了吧。
> 
> **Dr. Zhang：**这嘴和手，还真是我教出来的。再把“简单”勾上，“自我指涉”和“重复”他们没强调说明也不用了。
> 
> **Dr. Lee：**听您的。这图……还行，估计五分钟就能搞定了。
> 
>  **<五分钟后>**
> 
> **Dr. Zhang：**一二三四……四种颜色，不算太复杂。
> 
> **Dr. Lee：**还是要一百来号人呢。“队列”，“分散”，嗯……分成四组，每组二十六，然后把项目分散到每组里……
> 
> **Dr. Zhang：**每一个组都在不同站点就能保证交流尽量少了，但不知道怎么保证每个组之间的完全没有交流。按他们给的描述，感觉冒不起让项目重组的风险。
> 
> **Dr. Lee：**可能不至于//完全//不交流吧，再跑一次，然后“2-缺陷”。
> 
>  **Dr. Zhang：**看着还行。那就是“将项目分为四部分，每部分分散储存于26名D级人员记忆中，并保证每周每名D级人员接触到至多两名其他D级人员”。再细节的我私下里跟他们负责人讲吧。收工，把机子关了。
> 
> **<记录结束>**

**附录CN-2279-3：**来自研究员Nekah的信件，目前保存于Kempe有限计算处理中心主任办公室内

[[div class="page"]]
致继任者：
@@ @@
在基金会内，即使是我们所认为的//科学//也往往不在我们的掌控范围之内，但我彻底领悟到这一点的时候已经晚了。当年轻的Leppa找到我，也就是他的导师，并提出了一个听上去很荒唐的想法的时候，我并没有第一时间支持他。我知道在异常不被接受的帷幕之外，他和他的想法将会遭到无情的批驳，所以即使我已经在基金会内见识过许许多多不可能发生的事情，我还是认为难题依然会是难题。
@@ @@
但他从不这么认为。那只是他刚刚加入的第一个月，他肆意地汲取着数据库里的知识。时至今日我也不知道他究竟找到了什么，是哪个不引人注意的项目给了他启发。当他把第一版代码运行的结果展现在我眼前时，我似乎忘记了帷幕的存在。我知道这足以改变所有人对世界的认知，足以让他名垂青史，也足以让我同样被铭记。我骄傲地抬起头看到了他幸福的眼神，却没有丝毫自满。就是那一刻我意识到了我和Leppa的差别，也就在那一刻我知道不论我是否真的有帮助到他，这份成果也应该只属于他。
@@ @@
于是我下定决心，要尽我所能指导他将结果做到极致，禁得起任何人或者事物的反驳。我们随即开始了那一系列的测试，而各样问题也接踵而至。如果我们在帷幕之外，可能我们早就放弃了，或者我们欣然接受//科学//并不完全能被我们所用，我们也会更早就把程序销毁了。但我的野心，还有他对于//真相//的追求让我们走上了无法回头的道路。万幸的是，站点主管拉着伦理委员会的人停止了我们的测试。即使我从来都没有任何机会和伦理委员会里最低级别的人员平起平坐，我还是要说他们没有任何资格或者权限停止我们的测试，但我还是庆幸他们愿意出手，让那段疯狂的代码停了下来。
@@ @@
这对我来说是幸运的，对Leppa来说不是，那段代码是他的心血他的结晶。而他作为刚刚入职的新人就捅出了这么大的乱子，他不知道前方的道路是什么样的，甚至不知道前方是否还有路。也许当时我应该安慰他，告诉他所有人第一年的时候惹出来的麻烦远远不止他这样，可我又担心这样说会让他继续尝试捅穿那层帷幕。我想是时候停止了，我想告诉他即使没有这份成果，他的天分、热情、勤奋还是会带着他发现更多，因为他从来都没有惧怕过未知，而也许有一天他能找到一个稳定的方法，将帷幕之后的//科学//安全地带到众人面前。
@@ @@
然后他最后一次运行了代码，就在他的处罚决议会上。委员会的人和我通过气了，所以我知道他不会面对什么生理上的酷刑或者精神上的折磨，只是重新学习一遍《特殊收容措施标准拟定流程》。他似乎也知道了这会是他的处罚，在委员会面前阐述了一遍他对于特殊收容措施的理解。一开始还是那些陈词滥调，让委员会的人们都很满意。过了一会，他突然转向，在白板上疯狂地写下了满满的公式。没有人反应得过来，除了我。我当然知道他是什么意思，这太显然了。他停下了马克笔，在一片嘈杂声中看向了我。我想他看懂了我理解了他。然后，他走向电脑。然后，回车。
@@ @@
然后，消失。
@@ @@
委员会的人不愿意把会议厅内的白板拆下来搬到我的办公室里，他们可能还认为他的消失是什么诡计，甚至是叛变，所以必须要把所有东西都扣下来当作证据进行调查。于是我把白板上的内容誊写下来，顺便在经过几千层的申请之后把他的电脑也带了回去。我试图在他最后运行的代码里寻找让他消失的蛛丝马迹，但就算是一行不起眼的注释也并不存在。我不知道他是怎么消失的，就如同我无法理解他的第一版以及之后每一版代码那样。虽然在调查清楚后，他们否定了那些过于恶意的指摘，但他们还是把Leppa的离开定义为了一次事故。他们是错的。我知道他安排好了一切，做的无可指摘，所有代码写下来只为了一个目的，为了满足那些陈词滥调。
@@ @@
当然，现在来看这些陈词滥调对所有人来说都是必要的。为了控制帷幕之后的//真相//，我们必须制定有效的收容措施，这样才能保护大多数人。也许Leppa在某一刻领悟到了这一切，但这和他的信念又相违背，于是他做了取舍。
@@ @@
而我们只能继续。
[[>]]
控制，收容，保护
[[/>]]
@@ @@
[[>]]
Dr. Nekah
[[/>]]
[[/div]]

[[div class="footer-wikiwalk-nav"]]
[[=]]
<< [[[SCP-CN-2278]]] | SCP-CN-2279 | [[[SCP-CN-2280]]] >>
[[/=]]
[[/div]]