# Does exist NP language that is Cook Levin deterministic reducible to xor satisfiability in polynomial time?

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.

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).
• I want that $f$ is not identity function and the language that we reduce to XORSAT is not XORSAT. – user82913 Jan 24 '18 at 3:33