1
$\begingroup$

We say that the language $L$ is Cook Levin deterministic reducible to xor satisfiability in polynomial time if and only if for each word $w\in\Sigma^*:w\in L\iff f(w)\in XORSAT$ where $\Sigma=\{0,1\}$ and $f:\Sigma^*\rightarrow\Sigma^*$ is the function in the Cook Levin reduction that was introduced in 1971.

In other words if the language $L$ is Cook Levin deterministic reducible to xor satisfiability in polynomial time and $M$ is non deterministic Turing machine that decides the language $L$ in polynomial time then for each word $w\in\Sigma^*:\Phi_{M,w}$ is satisfiable if and only if $M$ accepts $w$, according to Cook Levin theorem since 1971, and also $\Phi_{M,w}$ is in XNF, i.e. XOR Normal Form.

Every boolean formula is in XOR Normal Form or XNF if and only if it is conjunction of clauses and each clause is XOR of literals.

It's well known, according to Cook Levin theorem since 1971, that every NP language is Cook Levin deterministic reducible to CNF satisfiability in polynomial time, i.e. if $L$ is arbitrary NP language and $M$ is non deterministic Turing machine that decides $L$ in polynomial time then for each word $w\in\Sigma^*:w\in L\iff f(w)\in CNFSAT\land\Phi_{M,w}$ is satisfiable if and only if $M$ accepts $w$ and $\Phi_{M,w}$ is necessarily in CNF, i.e. conjunctive normal form, that is conjunction of clauses and each clause is disjunction of literals.

But I don't know if exists special language that is in NP and if we apply the Cook Levin reduction then not only SAT instance is produced, but actually CNFSAT instance is produced and not only just CNFSAT instance is produced, but actually XORSAT instance is produced.

So my question is does exist special language in NP that after applying Cook Levin reduction, for each word $w\in\Sigma^*$, we get XORSAT instance?

Note that I don't want the function of the reduction to be identity and the NP language that needs to be found that it is Cook Levin reducible to XORSAT in polynomial time is not XORSAT itself.

Also the function of Cook Levin reduction isn't identity at all.

$\endgroup$

1 Answer 1

1
$\begingroup$

XORSAT is in P, so any such language would have to be in P as well.

As such, it is easy to exhibit such an example: the problem XORSAT itself satisfies all your requirements, as XORSAT is Cook-Levin reducible to XORSAT (let $f$ be the identity function).

$\endgroup$
4
  • $\begingroup$ I want that $f$ is not identity function and the language that we reduce to XORSAT is not XORSAT. $\endgroup$
    – user82913
    Jan 24, 2018 at 3:33
  • $\begingroup$ @user82913, I don't think that was specified in the question. If you have requirements you need to make sure that you list all of them in the question, so we don't spend time writing an answer that isn't useful to you. $\endgroup$
    – D.W.
    Jan 24, 2018 at 8:03
  • $\begingroup$ I will edit my question and add the requirement. $\endgroup$
    – user82913
    Jan 25, 2018 at 8:02
  • $\begingroup$ Note that the function of Cook Levin reduction isn't identity at all. $\endgroup$
    – user82913
    Jan 25, 2018 at 8:06

Your Answer

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