计算难度的比较——归约

计算难度的比较——归约

关于归约的故事

  计算难度的比较——归约

可以让机器人执行

计算难度的比较——归约

让机器人执行较困难,需要较高智能去判断(这不是归约方案)

计算难度的比较——归约

机器人执行比较容易(这才是归约方案)

可归约性

  一种化难为易、化繁为简的方法。

归约精确化

  计算难度的比较——归约

证明1

计算难度的比较——归约

证明2

多项式时间归约