计算复杂性理论初步(一)多项式时间归约 | 您所在的位置:网站首页 › 计算理论和计算复杂性理论一样吗 › 计算复杂性理论初步(一)多项式时间归约 |
一、归约的意义 求解一个算法问题的时候,我们往往可以直观地感受到有些问题是比较难的,有些问题是比较简单的,但是我们并不能因为没有设计出一个比较高效的算法,就说它是一个难问题,所以问题的难易是相对的,我们需要一个科学的手段来界定问题的难易 我们可以用问题之间的归约,来界定两个问题之间相对难易程度的基本手段
二、优化问题与判定问题 很多经典的难问题都是优化问题,而一个优化问题往往可以转换成对应的判定问题。 一般而言,优化问题是关注某种特殊的结构,并希望优化该结构的某种指标 最大团问题就是典型的优化问题、
一个优化问题往往可以定义其对应的判定问题。判定问题关注同样的结构、同样的指标,但是不同于优化问题的是,它不在关注指标的最大、最小值,而是引进一个参数k,并问一个“是与否”的问题 研究判定问题的意义是什么呢: 1、能为研究问题的复杂性发挥什么作用? 2、判定问题比优化问题更简单,那么研究判定问题能否全面反映该问题的复杂性
三、归约的定义 问题P可归约到问题Q:问题P可以间接地通过解决问题Q来实现
四、多项式时间 我们将多项式时间可解的问题称作P问题 对问题这样分类的意义? |
CopyRight 2018-2019 实验室设备网 版权所有 |