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$ – Dmitry Jan 25 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$ – ChaosPredictor Jan 25 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 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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