1 規(guī)約（reduction）

        一個(gè)從問題X到問題Y的規(guī)約：如果我們有一個(gè)問題Y的算法，我們可以用這個(gè)問題Y的算法來找到求解問題X的算法。

        我們可以使用規(guī)約來：

        1）找到解決問題的算法

        2）說明有一些問題我們無法找到有效的算法

1.1 語言的規(guī)約

 也就是說，這個(gè)規(guī)約算法輸入Lx中的語言w，輸出一個(gè)Ly中的語言w‘

1.2 決策問題的規(guī)約

        也就是說，這個(gè)規(guī)約算法輸入X中的語言Ix，輸出一個(gè)Y中的語言Iy

        或者說，如果輸入在X中是YES，那么輸出在Y中也是YES；如果輸入在X中是No，那么輸出在Y中也是NO

總結(jié)

以上是生活随笔為你收集整理的MAS 714 笔记20：规约和SAT的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。