CHAP9new

9.1 证明TIME(2n)=TIME(2n+1).

证明：2n=O(2n+1)? TIME(2n)?TIME(2n+1).

2n+1=O(2n)? TIME(2n+1)?TIME(2n). 所以 TIME(2n)=TIME(2n+1).

9.2证明TIME(2n)?TIME(22n)。注：这里“?”是严格包含。 证明：令f(n)=22n,则f(n)/logf(n)=22n/2n, 由时间层次定理有

TIME(o(22n/2n))?TIME(22n).

又由于2n=o(22n/2n)，TIME(2n)?TIME(o(22n/2n))，所以

TIME(2n)?TIME(22n).

9.3 证明NTIME(n)?PSPACE.

证明：NTIME(n)?NSPACE(n)?SPACE(n2)?SPACE(n3)?PSPACE. 9.6 证明若A?P，则PA＝P。

证明：首先P?PA。这是因为不带谕示即可。下面证明PA?P。 任取A?P，则存在多项式图灵机T判定A。

设B?PA，则存在带语言A的谕示的多项式时间图灵机MA判定B。如下构造不带谕示的图灵机D： D=“对于输入串w: 1) 在w上运行MA。

2) 每当MA要在谕示带上写下某个字符串x，则在x上运行T，若T接受，则代替谕示回答x属于A，否则代替谕示回答x不属于A。

3) 若MA接受，则接受；否则，拒绝。”

设MA的运行时间是na，T的运行时间是nb。谕示带上写下的字符串的长度不会超过na，询问谕示带的次数也不会超过na。D的运行时间是na (na)b=na+ab，所以A?P。

9.7 给出带指数的正则表达式，产生如下在字母表{0,1}上的语言： a. 所有长为500的字符串. (0?1)500。 b. 所有长度不超过500的字符串.(0?1??)500. c. 所有不少于500的字符串. (0?1)500(0?1)*.

d. 所有长度不等于500的字符串. (0?1??)499?(0?1)501(0?1)*. e. 所有恰好包含500个1的字符串. 0*(10*)500. f. 所有包含至少500个1的字符串. (0?1)*(1(0?1)*)500. g. 包含至多500个1的字符串. 0*((??1)0*)500.

h. 所有长度不少于500并且在第500个位置上是0的字符串. (0?1)4990(0?1)*.

i. 所有包含两个0并且其间至少相隔500个符号的字符串。(0?1)*0(0?1)500(0?1)*0(0?1)*.

9.8 若R是正则表达式，令R{m,n}代表表达式Rm?Rm+1 ?…?Rn，说明怎样用通常的指数算子实现算子R{m,n}，但不许用“…”。 答：设m

证明：A?NP?A?PSAT?Ac?PSAT?Ac?NP?CoNP?NP， A?CoNP?Ac?NP?Ac?PSAT?A?NP?NP?CoNP， 所以NP=CoNP.