证明此语言在NP $ CAP $ CONP中

Question

说$ 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 $的合适证人会有什么？

Answer 1

提示：使用以下事实：$ ell $是一对一的事实，因此，对于每个$ v $，都应对应一个唯一的$ u $，以便$ ell（u）= v $。