patternMinor
Is there such a notion as "effectively computable reductions" or would this be not useful
Viewed 0 times
thissuchnotioncomputableeffectivelywouldusefulreductionstherenot
Problem
Most reductions for NP-hardness proofs I encountered are effective in the sense that given an instance of our hard problem, they give a polynomial time algorithm for our problem under question by using reductions. All reductions in the 21 classic problems considered by R. Karp work this way. A very simple example might be reduction from INDEPENDENT_SET to CLIQUE, just built the complement graph of your input.
But when considering the proof of the famous Cook-Levin Theorem that SAT is NP-complete, the reduction starts from a non-deterministic TM and some polynomial, that exists by definition. But to me it is not clear how to get this polynomial effectively, meaning given an non-deterministic TM from which I know it runs in polynomial time, it is not clear how to compute this polynomial, and I highly suspect it is not computable at all.
So soley from the encoding of NP-complete problems by the class of non-deterministic polynomial time TMs (the polynomial itself is not encoded as far as I know) I see no way how to give a reduction in an effective way, the aforementioned proof just shows that there exists some, but not how to get it.
Maybe I have understood something wrong, but I have the impression that usually the reductions given are stronger in the sense that they are indeed computable, i.e. given a problem we can compute our reduction, and not merely know its existence.
Has this ever been noted? And if so, is there such a notion as "effectively computable reduction", or would it be impractical to restrict reductions to be itself computable? For me, from a more practical perspective, and also the way I sometimes see reductions introduced ("like we have an algorithm to convert one instance to another") it would be highly desirable to know how to get this algorithm/reduction, so actually it seems more natural to demand it, but why is it not done?
But when considering the proof of the famous Cook-Levin Theorem that SAT is NP-complete, the reduction starts from a non-deterministic TM and some polynomial, that exists by definition. But to me it is not clear how to get this polynomial effectively, meaning given an non-deterministic TM from which I know it runs in polynomial time, it is not clear how to compute this polynomial, and I highly suspect it is not computable at all.
So soley from the encoding of NP-complete problems by the class of non-deterministic polynomial time TMs (the polynomial itself is not encoded as far as I know) I see no way how to give a reduction in an effective way, the aforementioned proof just shows that there exists some, but not how to get it.
Maybe I have understood something wrong, but I have the impression that usually the reductions given are stronger in the sense that they are indeed computable, i.e. given a problem we can compute our reduction, and not merely know its existence.
Has this ever been noted? And if so, is there such a notion as "effectively computable reduction", or would it be impractical to restrict reductions to be itself computable? For me, from a more practical perspective, and also the way I sometimes see reductions introduced ("like we have an algorithm to convert one instance to another") it would be highly desirable to know how to get this algorithm/reduction, so actually it seems more natural to demand it, but why is it not done?
Solution
Nice question! I think that your notion of an "effectively computable reduction" is interesting and worth studying, but not as fundamental as standard reductions. Let me provide some observations about this notion that may be illuminating:
Observation 1: it does not make sense to talk about effectively computable reductions from one language to another; only from a family of languages to another.
In particular, you seem to be mixed up when you write this:
Most reductions for NP-hardness proofs I encountered are effective in the sense that given an instance of our hard problem, they give a polynomial time algorithm for our problem under question by using reductions. All reductions in the 21 classic problems considered by R. Karp work this way.
A reduction from, say, VertexCover to 3SAT is a Turing machine $f$ that transforms instances of VertexCover into instances of 3SAT. Since it is a Turing machine, it is effectively computable by definition. So it is not surprising that all reductions you have seen of this form are effectively computable.
In other words, if we just look at reductions from one language to another, then every reduction is effectively computable!
This is different from the case of the Cook-Levin theorem, where we have to show a reduction $f$ from an arbitrary NP language to SAT. Then it might make sense to consider whether this reduction -- parameterized by the language in NP -- is effective or not. But that brings us to my second point:
Observation 2: What counts as an effectively computable reduction depends on the representation of languages.
This is important because standard reductions (either many-to-one reductions or Turing reductions) do not depend on the way the language is represented. For a reduction from $L$ to $L'$, I consider $L$ and $L'$ to be subsets of $\{0, 1\}^*$. But for your notion of effectively computable to make sense, we need to have access to a representation of $L$ (we probably don't need a representation of $L'$).
To make this point clearer, consider the reduction in the proof of the Cook-Levin theorem, which you brought up. The proof considers a language $L$, represented by a polynomial-time nondeterministic Turing machine $N$. Then it shows that $L$ is reducible to SAT. You say that this reduction is not effectively computable, but that depends on how $N$ is represented, i.e., the definition of a polynomial-time nondeterminstic Turing machine $N$:
-
Definition 1: A polynomial-time NTM is a nondeterministic Turing machine such that there exists a polynomial $p(n)$, such that the TM always halts in time at most $p(n)$.
-
Definition 2: A polynomial-time NTM consists of a nondeterministic Turing machine, together with a polynomial $p(n)$. The way it runs is that, on any branch, it is only executed for $p(n)$ steps; if it does not halt in this time, then that branch is ignored.
It may seem that I am making Definition 2 up and that the definition is not natural, but actually both of these are perfectly valid definitions of a polynomial-time NTM that both have their merits. And for the classical theory of P, NP, and NP-completeness, both of these definitions are equivalent. The nice thing about Definition 2 is that an NTM is allowed to diverge on certain branches; you don't worry about that because the execution semantics says that we just forget about it once the running time goes above $p(n)$.
However, the definitions become inequivalent when it comes to effectively computable reductions. Note that, according to Definition 1, when we are given a language defined by an NTM $N$, we have no idea what its running time is, so we may not be able to reduce it to SAT (more on this below). But according to Definition 2, part of the NTM $N$ is that it comes with a polynomial, and so we know its running time. Therefore, we can effectively reduce all NP languages to SAT if we are using Definition 2.
Also, we have only considered nondeterministic Turing machines; we could equivalently define NP using verifier Turing machines. Then the definition of an effectively computable reduction could be something else!
TL;DR: Depending on how a language in NP is represented, and in particular depending on the definition of a polynomial-time NTM, it may be either true or false that every language in NP is effectively reducible to SAT. In other words, The set of effectively computable reductions changes depending on the model of computation used to represent languages in NP.
Now at this point, given points (1) and (2), a question still remains: can the reduction in the Cook-Levin theorem be made to be effective? In particular, suppose we fix the following definitions:
-
Languages in NP are represented by nondeterministic Turing machines whose runtime is bounded by an unknown polynomial $p$ (i.e. Definition 1).
-
Given a language $L$, we say that the class of languages NP is effectively poly-time reducible to $L$ if the following holds: there is a TM $f$ that takes as
Observation 1: it does not make sense to talk about effectively computable reductions from one language to another; only from a family of languages to another.
In particular, you seem to be mixed up when you write this:
Most reductions for NP-hardness proofs I encountered are effective in the sense that given an instance of our hard problem, they give a polynomial time algorithm for our problem under question by using reductions. All reductions in the 21 classic problems considered by R. Karp work this way.
A reduction from, say, VertexCover to 3SAT is a Turing machine $f$ that transforms instances of VertexCover into instances of 3SAT. Since it is a Turing machine, it is effectively computable by definition. So it is not surprising that all reductions you have seen of this form are effectively computable.
In other words, if we just look at reductions from one language to another, then every reduction is effectively computable!
This is different from the case of the Cook-Levin theorem, where we have to show a reduction $f$ from an arbitrary NP language to SAT. Then it might make sense to consider whether this reduction -- parameterized by the language in NP -- is effective or not. But that brings us to my second point:
Observation 2: What counts as an effectively computable reduction depends on the representation of languages.
This is important because standard reductions (either many-to-one reductions or Turing reductions) do not depend on the way the language is represented. For a reduction from $L$ to $L'$, I consider $L$ and $L'$ to be subsets of $\{0, 1\}^*$. But for your notion of effectively computable to make sense, we need to have access to a representation of $L$ (we probably don't need a representation of $L'$).
To make this point clearer, consider the reduction in the proof of the Cook-Levin theorem, which you brought up. The proof considers a language $L$, represented by a polynomial-time nondeterministic Turing machine $N$. Then it shows that $L$ is reducible to SAT. You say that this reduction is not effectively computable, but that depends on how $N$ is represented, i.e., the definition of a polynomial-time nondeterminstic Turing machine $N$:
-
Definition 1: A polynomial-time NTM is a nondeterministic Turing machine such that there exists a polynomial $p(n)$, such that the TM always halts in time at most $p(n)$.
-
Definition 2: A polynomial-time NTM consists of a nondeterministic Turing machine, together with a polynomial $p(n)$. The way it runs is that, on any branch, it is only executed for $p(n)$ steps; if it does not halt in this time, then that branch is ignored.
It may seem that I am making Definition 2 up and that the definition is not natural, but actually both of these are perfectly valid definitions of a polynomial-time NTM that both have their merits. And for the classical theory of P, NP, and NP-completeness, both of these definitions are equivalent. The nice thing about Definition 2 is that an NTM is allowed to diverge on certain branches; you don't worry about that because the execution semantics says that we just forget about it once the running time goes above $p(n)$.
However, the definitions become inequivalent when it comes to effectively computable reductions. Note that, according to Definition 1, when we are given a language defined by an NTM $N$, we have no idea what its running time is, so we may not be able to reduce it to SAT (more on this below). But according to Definition 2, part of the NTM $N$ is that it comes with a polynomial, and so we know its running time. Therefore, we can effectively reduce all NP languages to SAT if we are using Definition 2.
Also, we have only considered nondeterministic Turing machines; we could equivalently define NP using verifier Turing machines. Then the definition of an effectively computable reduction could be something else!
TL;DR: Depending on how a language in NP is represented, and in particular depending on the definition of a polynomial-time NTM, it may be either true or false that every language in NP is effectively reducible to SAT. In other words, The set of effectively computable reductions changes depending on the model of computation used to represent languages in NP.
Now at this point, given points (1) and (2), a question still remains: can the reduction in the Cook-Levin theorem be made to be effective? In particular, suppose we fix the following definitions:
-
Languages in NP are represented by nondeterministic Turing machines whose runtime is bounded by an unknown polynomial $p$ (i.e. Definition 1).
-
Given a language $L$, we say that the class of languages NP is effectively poly-time reducible to $L$ if the following holds: there is a TM $f$ that takes as
Context
StackExchange Computer Science Q#121136, answer score: 6
Revisions (0)
No revisions yet.