正在加载图片...
问题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)E P 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 fi2 and f21 such that for any iI,we have fi2(e1(i))=e2(i) andf21(e2(i)=e1(i).5 证明要点:两次多项式时间的计算的串行组合,仍然是 多项式时间的问题1:这个定理想说明的道理是什么? 证明要点:两次多项式时间的计算的串行组合,仍然是 多项式时间的
<<向上翻页向下翻页>>
©2008-现在 cucdc.com 高等教育资讯网 版权所有