说$ ell: {0,1 }^ ast to {0,1 }^ ast $是保留长度的一对一的多项式计算函数。考虑语言$$ l = bigl {v ; big | ; 存在u: bigl(u_1 = 1 ~~ text {and} ~~ ell(u)= v bigr) bigr }。$ $我如何证明$ l $ in $ mathsf { np} cap mathsf {conp} $?基本上,$ mathsf {np} $和$ mathsf {conp} $ be in $ mathsf {np} $中的$ l $的合适证人会有什么?

有帮助吗?

解决方案

提示:使用以下事实:$ ell $是一对一的事实,因此,对于每个$ v $,都应对应一个唯一的$ u $,以便$ ell(u)= v $。

许可以下: CC-BY-SA归因
不隶属于 cs.stackexchange
scroll top