1701006292
图4-12 角AOB二等分 图4-13 角AOD三等分 如图4-12所示，对于二等分一个角AOB，采用尺规作图划分平均线是很容易得到的。但是对于如图4-13所示的三等分角而言，问题就没那么容易了，三等分顾名思义就是一个角需要除以3，而3是质数，对于任意的角θ而言，不能保证是有理数的，因此三等分任意角成为一个尺规作图难题，已经有人证明，此命题“采用尺规作图，三等分任意角”是不成立的。
1701006293
1701006294
（3）倍立方——求作一立方体使其体积是一已知立方体体积的二倍
1701006295
1701006296
如图4-14所示为一个小立方体，其体积等于如图4-15所示立方体体积的一半。
1701006297
1701006298
1701006299
1701006300
1701006301
1701006302
1701006303
图4-14 立方体1 图4-15 立方体2 这个问题可以等效为，其中a为如图4-14所示立方体的边长，b为如图4-15所示的立方体的边长，要使成立，则就是为无理数，因此很难用尺规作图得到一立方体使其体积是一已知立方体体积的二倍，已经有人证明，此命题“采用尺规作图，求作一立方体使其体积是一已知立方体体积的二倍”是不成立的。
1701006304
1701006305
（4）做正十七边形
1701006306
1701006307
采用尺规作图，大家对于正三角形和正六边形等绘图，很轻松就能解决，但是对于正十七边形，这个问题就变得相当复杂了。让我们先来感知一下正十七边形的图形，采用MATLAB编程如下：
1701006308
1701006309
clc,clear,close all %清屏和清除变量 warning off %消除警告 %画正十七边形 cita = 0:2*pi/16:2*pi; %角度取值 for i=1:17 x(i)=30*cos(cita(i)); %画正十七边形的坐标x y(i)=30*sin(cita(i)); %画正十七边形的坐标y end plot(x,y,‘r’,‘linewidth’,2) %画正十七边形 hold on %保持图像句柄，继续画图 cita1 = 0:0.01:2*pi; %角度取值 for i=1:length(cita1) x1(i)=30*cos(cita1(i)); %画圆的坐标y y1(i)=30*sin(cita1(i)); %画圆的坐标y end plot(x1,y1,‘b’,‘linewidth’,2) %画圆 grid on
1701006310
1701006311
运行程序输出图形如图4-16所示。
1701006312
1701006313
1701006314
1701006315
1701006316
图4-16 正十七边形
1701006317
1701006318
如图4-16所示为正十七边形图形，绘制正十七边形，相当于7等分一个平角，一个平角为180度，这个问题就显得很直接明了。平分一个角度，7等分，有点像“尺规作图（2）三等分任意角”这个命题，7等分角度，采用尺规作图是否成立，得依靠实际证明。
1701006319
1701006320
对于这个问题，高斯用代数的方法解决了该问题。
1701006321
1701006322
1801年，高斯证明：如果k是费马数，那么就可以用直尺和圆规将圆周k等分。高斯本人就是根据这个定理作出了正十七边形，解决了两千年来悬而未决的难题。
1701006323
1701006324
高斯视此为生平得意之作，还交待死后要把正十七边形刻在他的墓碑上，但后来他的墓碑上并没有刻上十七边形，而是十七角星，因为负责刻碑的雕刻家认为，正十七边形和圆太像了，大家一定分辨不出来。
1701006325
1701006326
因此，命题“采用尺规作图，做正十七边形”是成立的。
1701006327
1701006328
1701006329
1701006330
1701006331
我和数学有约：趣味数学及算法解析 [:1701004205]
1701006332
我和数学有约：趣味数学及算法解析 4.11 P/NP问题
1701006333
1701006334
P/NP问题是在理论信息学中计算复杂度理论领域里至今没有解决的问题，它被“克雷数学研究所”（Clay Mathematics Institute，简称CMI）在千禧年大奖难题中收录。P/NP问题中包含了复杂度类P与NP的关系。1971年史提芬·古克（Stephen A．Cook）和Leonid Levin相对独立的提出：是否两个复杂度类P和NP是恒等的？
1701006335
1701006336
复杂度类P包含所有那些可以由一个确定型图灵机在多项式表达的时间内解决的问题；类NP由所有其肯定解可以在给定正确信息的多项式时间内验证的决定问题组成，或者等效的说，那些解可以在非确定图灵机上在多项式时间内找出的问题的集合。
1701006337
1701006338
【问题】那么，P和NP相等吗?
1701006339
1701006340
【分析】
1701006341