计算复杂性 (Fall 2019)/Assignment 3: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
imported>TCSseminar
No edit summary
imported>TCSseminar
No edit summary
Line 9: Line 9:


Deadline: 10月24日上课前。
Deadline: 10月24日上课前。
来不及完成作业的同学可以通过邮件说明情况申请适量延期。

Revision as of 00:40, 24 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日上课前。 来不及完成作业的同学可以通过邮件说明情况申请适量延期。