正在加载图片...
问题1:这个定理想说明的道理是什么? Lemma 34.1 Let O be an abstract decision problem on an instance set I,and let el and e2 be polynomially related encodings on I.Then,e1(O)EP if and only if e2(O)E P. For some set I of problem instances,we say that two en- codings e and e2 are polynomially related if there exist two polynomial-time com- putable functions f12 and f21 such that for any i 1,we have fi2(e1(i))=e2(i) andf21(e2(i)=e1(i).5问题1:这个定理想说明的道理是什么?
<<向上翻页向下翻页>>
©2008-现在 cucdc.com 高等教育资讯网 版权所有