# Cook–Levin theorem and reduction as injective function

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

• 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? – Dmitry Jan 25 at 18:21
• @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 – ChaosPredictor Jan 25 at 21:09
• 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. – D.W. Jan 26 at 5:04

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.