1.1 划分的难题

看下边38个数字:

14 175, 15 055, 16 616, 17 495, 18 072, 19 390, 19 731, 22 161, 23 320, 23 717, 26 343, 28 725, 29 127, 32 257, 40 020, 41 867, 43 155, 46 298, 56 734, 57 176, 58 306, 61 848, 65 825, 66 042, 68 634, 69 189, 72 936, 74 287, 74 537, 81 942, 82 027, 82 623, 82 802, 82 988, 90 467, 97 042, 97 507, 99 564

这38个数字之和为2 000 000。你能把它们平分成两组,每组19个数字之和分别为1 000 000吗?你可以使用计算器、电子表格或写一个计算机程序。(答案在本章最后。)

不那么简单,是吧?把这些数分成两组有170亿种方式。如果程序编得巧妙,使用当今较快的计算机能够找到一个解。但如果给你3800个数,或者3800万个数呢?短小的计算机程序可没法给出答案了!

这只是个无意义的数学谜题吗?就算存在一个厉害的计算机程序,它能解决这个平分数组的问题(假设有解),那又如何呢?如果是这样的话,我们能用这个程序做更多的事。这个程序能解决所有的问题,包括旅行推销员问题。这个简短的难题抓住了P/NP问题的本质:一个程序如果能解决这个难题的复杂版本,那么它也能解出任意问题。

目录