patternMinor
There are parsimonious reductions between all NP-Complete problems: Well-known conjecture?
Viewed 0 times
allareproblemsconjecturecompletebetweenwellknownreductionsthere
Problem
The reduction from SAT to Clique shows a way to construct a graph with cliques from a Boolean formula. A closer look at that reduction even yields a simple algorithm which finds a large clique in the graph from a given satisfying assignment to the variables. That mapping is bijective: each satisfying assignment is mapped to a different large clique, and the number of large cliques is the same as the number of satisfying assignments.
A reduction which preserves the number of solutions is called a parsimonious reduction (technical definition below). It is a stronger notion of reduction than the usual Karp reductions, because not all reductions have that property. NP-Completeness is usually defined in terms of Karp-reductions, but since parsimonious reductions are clearly more beautiful, it is natural to conjecture:
Conjecture: All NP-Complete problems can be reduced to one another via parsimonious reductions.
But I can't find this in the literature.
Question: Does the literature contain the conjecture that all NP-Complete languages can be reduced to eachother via parsimonious reductions?
This is different from the Bertman-Hartmanis conjecture that all NP-Complete problems can be reduced to eachother via polynomial-time invertible bijections. That conjecture is about instances of the language, whereas I talk about certificates to the NP machine. Of course the most beautiful thing would be a parsimonious bijection! References to that are greatly appreciated.
Definition If $L,K\subseteq\{0,1\}^\ast$ are languages and $f\colon\{0,1\}^\ast\to\{0,1\}^\ast$ is a reduction from $L$ to $K$, then we say that $f$ is parsimonious if there are polynomial-time nondeterministic Turing Machines $N, M$ accepting $L$ and $K$, respectively such that for all $x\in\{0,1\}^\ast$, $\#N(x)=\#M(f(x))$, where $\#N(x)$ denotes the number of certificates accepted by a non-deterministic Turing Machine on input $x$.
(The motivation for the question is that, for my thesis, I found that the r
A reduction which preserves the number of solutions is called a parsimonious reduction (technical definition below). It is a stronger notion of reduction than the usual Karp reductions, because not all reductions have that property. NP-Completeness is usually defined in terms of Karp-reductions, but since parsimonious reductions are clearly more beautiful, it is natural to conjecture:
Conjecture: All NP-Complete problems can be reduced to one another via parsimonious reductions.
But I can't find this in the literature.
Question: Does the literature contain the conjecture that all NP-Complete languages can be reduced to eachother via parsimonious reductions?
This is different from the Bertman-Hartmanis conjecture that all NP-Complete problems can be reduced to eachother via polynomial-time invertible bijections. That conjecture is about instances of the language, whereas I talk about certificates to the NP machine. Of course the most beautiful thing would be a parsimonious bijection! References to that are greatly appreciated.
Definition If $L,K\subseteq\{0,1\}^\ast$ are languages and $f\colon\{0,1\}^\ast\to\{0,1\}^\ast$ is a reduction from $L$ to $K$, then we say that $f$ is parsimonious if there are polynomial-time nondeterministic Turing Machines $N, M$ accepting $L$ and $K$, respectively such that for all $x\in\{0,1\}^\ast$, $\#N(x)=\#M(f(x))$, where $\#N(x)$ denotes the number of certificates accepted by a non-deterministic Turing Machine on input $x$.
(The motivation for the question is that, for my thesis, I found that the r
Solution
Yes, it is well known conjecture. Oded Goldreich states the fact that "all known reductions among natural $NP$-complete problems are either parsimonious or can be easily modified to be so". ( Computational Complexity: A Conceptual Perspective By Oded Goldreich).
Context
StackExchange Computer Science Q#77957, answer score: 2
Revisions (0)
No revisions yet.