如果我们定义一个从语言 A 到语言 B 的多项式时间归约 R：对于每个 x，归约 R 在输入 x 上的输出 R(x) 是一个长度为 |R(x)| 的字符串。 ≤ O(log |x|)。如果从 CLIQUE 到 NP 中的语言 L 存在这种归约，我们是否可以证明 NP 属于 QP？ （QP 是准多项式时间复杂度类。）
为了证明 NP ⊆ QP 在多项式时间从 CLIQUE 减少到 L 的假设下，我需要证明 NP 中的任何语言 L' 都可以由确定性图灵机在准多项式时间内决定，该图灵机可以访问oracle for L. 然后就不知道怎么继续了。谢谢！