0
$\begingroup$

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

Improve this question
$\endgroup$
3
  • 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
    Commented 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$
    – ChaosPredictor
    Commented 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. ♦
    Commented Jan 26, 2021 at 5:04

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

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.