I saw that the injectivity "derives directly from the theorem", but i can't see how it's happen, any explanation?

  • 1
    $\begingroup$ I'm not sure what exactly do they mean, but isn't it true that the resulting circuit can only be constructed from a unique nondeterministic TM? $\endgroup$
    – user114966
    Jan 25, 2021 at 18:21
  • $\begingroup$ @Dmitry Thank you, I think it's not about TM, maybe the answer to this question is: to each CNF can be added one or more clauses that make it possible map each unique domain to unique codomain. but I'm not sure $\endgroup$ Jan 25, 2021 at 21:09
  • 3
    $\begingroup$ Can you edit your question to provide more context and background? I'm not sure what your question is asking, and I don't know where you read that quote or the context or what it is referring to, so it's hard to know how to answer. $\endgroup$
    – D.W.
    Jan 26, 2021 at 5:04

1 Answer 1


Your question is a bit unclear, but let me hazard a guess. Let $L$ be an NP language. According to the Cook–Levin theorem, there is a polynomial time reduction $\phi_L$ from $L$ to SAT, that is, $\phi_L$ is a polynomial time function that satisfies $x \in L$ iff $\phi_L(x) \in \mathrm{SAT}$. You are asking why $\phi_L$ is injective.

Roughly speaking, $\phi_L(x)$ constructs a formula which describes the operation of a nondeterministic Turing machine for $L$ executing on $x$. The input $x$ is hardcoded in this description, and in particular, we can extract $x$ from $\phi_L(x)$. This implies that $\phi_L$ is injective.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.