计算复杂性 (Fall 2019)/Assignment 3: Difference between revisions
Jump to navigation
Jump to search
imported>TCSseminar No edit summary |
imported>TCSseminar No edit summary |
||
| Line 3: | Line 3: | ||
Exercise 4.2, 4.3, 4.5, 4.9, 4.11, 4.7 (bonus), 4.12 (bonus). | Exercise 4.2, 4.3, 4.5, 4.9, 4.11, 4.7 (bonus), 4.12 (bonus). | ||
4.3 题目有错。将题目中 complete 一词改为 hard。本题需要证明任何一个非空也非<math>\{0,1\}^*</math>的语言在 polynomial-time Karp reduction 下<font color=red><strong>都</strong></font>是 NL- | 4.3 题目有错。将题目中 complete 一词改为 hard。本题需要证明任何一个非空也非<math>\{0,1\}^*</math>的语言在 polynomial-time Karp reduction 下<font color=red><strong>都</strong></font>是 NL-hard，也就是证明<math>\forall L\notin\{\emptyset,\{0,1\}^*\},\forall L'\in\mathbf{NL},L'\le_p L</math>。 | ||
请将作业的电子版本(pdf、扫描或拍照)发送到助教处([mailto:liu.mingmou@smail.nju.edu.cn liu.mingmou@smail.nju.edu.cn])，'''文件名请使用自己的学号+姓名，学号放在最前面'''，中英文不限。 | 请将作业的电子版本(pdf、扫描或拍照)发送到助教处([mailto:liu.mingmou@smail.nju.edu.cn liu.mingmou@smail.nju.edu.cn])，'''文件名请使用自己的学号+姓名，学号放在最前面'''，中英文不限。 | ||
Revision as of 04:25, 22 October 2019
Chapter 4.
Exercise 4.2, 4.3, 4.5, 4.9, 4.11, 4.7 (bonus), 4.12 (bonus).
4.3 题目有错。将题目中 complete 一词改为 hard。本题需要证明任何一个非空也非[math]\displaystyle{ \{0,1\}^* }[/math]的语言在 polynomial-time Karp reduction 下都是 NL-hard，也就是证明[math]\displaystyle{ \forall L\notin\{\emptyset,\{0,1\}^*\},\forall L'\in\mathbf{NL},L'\le_p L }[/math]。
请将作业的电子版本(pdf、扫描或拍照)发送到助教处(liu.mingmou@smail.nju.edu.cn)，文件名请使用自己的学号+姓名，学号放在最前面，中英文不限。
Deadline: 10月24日上课前。