正在加载图片...
7/8-approximation of 3SAT Since 3SAT appears too hard in its full generality,let's aim lower. 3SAT asks whether there is an assignment satisfying all clauses. ■ Can you find an assignment satisfying half of the clauses? Let's run an example where you give an input instance you give a solution! 67/8-approximation of 3SAT ◼ Since 3SAT appears too hard in its full generality, let’s aim lower. ◼ 3SAT asks whether there is an assignment satisfying all clauses. ◼ Can you find an assignment satisfying half of the clauses? ◼ Let’s run an example where ❑ you give an input instance ❑ you give a solution! 6
<<向上翻页向下翻页>>
©2008-现在 cucdc.com 高等教育资讯网 版权所有