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

From EtoneWiki
Jump to: navigation, search
(Created page with "Chapter 4. Exercise 4.2, 4.3, 4.5, 4.9, 4.11, 4.7 (bonus), 4.12 (bonus). 请将作业的电子版本(pdf、扫描或拍照)发送到助教处([mailto:liu.mingmou@smail.nju....")
 
 
Line 2: Line 2:
  
 
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 下是 NL-hard。
  
 
请将作业的电子版本(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]),'''文件名请使用自己的学号+姓名,学号放在最前面''',中英文不限。

Latest revision as of 04:23, 13 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。本题需要证明任何一个非空也非的语言在 polynomial-time Karp reduction 下是 NL-hard。

请将作业的电子版本(pdf、扫描或拍照)发送到助教处(liu.mingmou@smail.nju.edu.cn),文件名请使用自己的学号+姓名,学号放在最前面,中英文不限。


Deadline: 10月24日上课前。