NP, NP-completeness (3)# Thoughts - 思考者
wy
1 楼
先来一点补充：
Church's Thesis: 所有通用计算机可以解决的问题，图灵机都
可以解决，换句话说就是图灵机的计算能力和通用计算机完全一样，
不多也不少。所以我们才可以使用图灵机解决以下问题：可计算性与
计算复杂性。
可计算性就是说，什么问题是计算机可以解决的，而什么问题是不可以的。
计算复杂性就是说，对于可以解决的问题，我们可以以什么样的成本去解决。
计算复杂性的问题，首先说一下为什么计算机科学家认为NP问题
对于决定性机器而言其产生的障碍是本质的。
举个例子，如果我们假定n=1时为了解决问题，计算机需要执行1条指令，
在假设每条指令执行时间等长，那么n=2时，对于一个NP问题，计算机需要
执行2条指令...那么n=n1时，计算机就需要执行2^(n-1)条指令，现在
我们就算有一台无比强大的机器，他的速度达到2^10000指令/秒，可是，
如果这时候n=100000,他的执行时间仍然达到2^90000秒！大家可以试试，
如果一个多项式时间的算法，情况如何。
计算复杂性问题可以通过量子计算机（非决定性图灵机）得到缓解，但是
不是解决！因为除了NP class,还存在有成本更高
Church's Thesis: 所有通用计算机可以解决的问题，图灵机都
可以解决，换句话说就是图灵机的计算能力和通用计算机完全一样，
不多也不少。所以我们才可以使用图灵机解决以下问题：可计算性与
计算复杂性。
可计算性就是说，什么问题是计算机可以解决的，而什么问题是不可以的。
计算复杂性就是说，对于可以解决的问题，我们可以以什么样的成本去解决。
计算复杂性的问题，首先说一下为什么计算机科学家认为NP问题
对于决定性机器而言其产生的障碍是本质的。
举个例子，如果我们假定n=1时为了解决问题，计算机需要执行1条指令，
在假设每条指令执行时间等长，那么n=2时，对于一个NP问题，计算机需要
执行2条指令...那么n=n1时，计算机就需要执行2^(n-1)条指令，现在
我们就算有一台无比强大的机器，他的速度达到2^10000指令/秒，可是，
如果这时候n=100000,他的执行时间仍然达到2^90000秒！大家可以试试，
如果一个多项式时间的算法，情况如何。
计算复杂性问题可以通过量子计算机（非决定性图灵机）得到缓解，但是
不是解决！因为除了NP class,还存在有成本更高