5
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ Nice question! I think one can construct an effective Cook reduction, by iterative doubling. Does that help? (Nitpick: I suspect this is about constructiveness not about computability: there are functions that we know are computable but where we don't know how to constructively provide an algorithm for them.) $\endgroup$ – D.W. Feb 25 at 18:26
  • $\begingroup$ Yes, maybe it is more about how to interpret the exists-quantifier more constructively. Your remark about "iterative doubling" does not really help, googling does not reveal anything related, and otherwise if I get you right you mean "allocating" space/"SAT variables" as necessary in an "iterative doubling" way, okay than it might be something like 2(p(n)+1) to much space allocated, but with this procedure I think you would capture all subexponential running times too, not just the polynomial ones, but maybe I have understood you simply wrong on that... $\endgroup$ – StefanH Feb 25 at 20:43
5
$\begingroup$

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 input $\langle N, w \rangle$, where $N$ is a polynomial-time NTM and $w$ is any input to $N$, such that $w \in L(N)$ if and only if $f(\langle N, w \rangle) \in L$. Also, $f$ must run in polynomial time (in its input $\langle N, w \rangle$).

In other words, to address point (1), we are assuming that languages in NP are represented by nondeterministic Turing machines without an explicit polynomial bound. And to address point (2), in our definition of effectively reducible, we are talking about a reduction from a class of languages, in this case NP, to a single language. Now we have the following observation:

Observation 3: (Cook-Levin is not effective) The class NP is NOT effectively reducible to SAT.

Let us see why this is true. Assume towards a contradiction that an effective reduction $f$ exists. The idea is that we will try to solve a difficult (say, doubly-exponential-time) problem by taking its instance, turning it into a polynomial-time NTM, and asking $f$ to reduce it to SAT. So, let $L_{hard}$ be some problem that requires doubly-exponential time to solve (this exists by the Time Hierarchy theorem), and let $M_{hard}$ be a (deterministic) TM that solves it. Given any instance $w$ of the problem, define the following NTM $N_w$: \begin{align*} N_w := &\text{"On any input $a$, first run } M_{hard} \\ &\text{on input } w \text{. When it halts, accept if} \\ &\text{it accepts and reject if it rejects."} \end{align*}

Now we can use this to solve $L_{hard}$ in exponential time (not double exponential), as follows. On input $w$, we first construct $N_w$, which has size only a constant more than $w$. Then we pass $\langle N_w, \epsilon \rangle$ (the second argument, $\epsilon$, is just a placeholder here) to $f$ to reduce it to SAT. $f$ gives us back an instance of SAT that is at most polynomial size in $N_w$, and $f$ takes only polynomial time to run. So we end up with an instance of SAT of polynomial size in $w$; now we solve it in exponential time in $w$ using brute-force search.


This point (3) seems to suggest that most of the time, no interesting class of languages will be reducible in this effectively computable sense to a single language. It will just be too hard, because you can exploit this computability to then solve hard problems by encoding them as part of a TM input to the effective reduction. However, something is a bit fishy here, because if we feed the TMs $N_w$ into the Cook-Levin theorem reduction, we would end up with very large SAT formulas, exponential in $w$. So perhaps our definition needs to be tweaked so that $f$ runs in time polynomial in the running time of $N_w$, not just polynomial in the input $\langle N_w, \epsilon \rangle$.

Observation 4: If we allow Turing (many to many) reductions, then Cook-Levin can be made effective.

As D.W. says in a comment:

I think one can construct an effective Cook reduction, by iterative doubling. Does that help?

I also believe this is true. In particular, we can change our definition of an "effective reduction" from NP to a language $L$ by saying that the reduction does not just return an instance of $L$, but returns many instances of $L$ in sequence, and uses an oracle for $L$ to solve the original problem. Then to solve a general problem in NP, you could try larger and larger polynomials $p$ until you get the right one which bounds the running time. You can detect whether a particular polynomial bounds the running time on all branches of the NTM by a separate reduction to SAT.

Disclaimer

I am not an expert in this topic. These are just some preliminary notes on the idea, and I am not sure if someone has studied this in the literature.

P.S. Although it may not be directly related, your question about considering effective reductions reminds me of an idea I had, about considering not just whether languages are in P or in NP, but whether they are provably so. This is related to the idea of developing a complexity theory that is effective or constructive. I asked and later answered question about defining provably P and provably NP languages here.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for the detailed answer, that clarified a lot! Regarding your last observations, the reduction from NTM's to SAT can then produce instances $L_1, L_2, L_3, \ldots$ where it has successively tried the polynomials for example $n, n^2, n^3,\ldots$ if I got you right. But I am somewhat unsure about you saying "can detect wheter a particular polynomial bounds the running time on all branches", I think this just holds if the NTM also stops on all branches [or entering some states signaliing the end of the computation]. [...] $\endgroup$ – StefanH Feb 26 at 12:26
  • $\begingroup$ [...] But as far as I understood this is just guaranteed if the NTM does not accepts the input, because then every path/branch must terminate and give non-acceptance. But in case we accept the input, it is just required that some branch stops in an accepting state, but still we could have branches that run infinitely long in this case. How do you handle that? $\endgroup$ – StefanH Feb 26 at 12:28
  • $\begingroup$ Also a formula that checks all branches for some polynomial has to have variables for all possible configurations, which is expontial, i.e. the formula would have size $c^{p(n})$ for the supposed polynomial (and $c$ depending on the number of choices, i.e. $c = 2$ for binary branching), so this would not give a polynomial time reduction... $\endgroup$ – StefanH Feb 26 at 12:38
  • $\begingroup$ But beside from that, I liked your observation about dependency on the representation. Somehow came to my mind that this is a speciality (or oddity) of the NTM-way of defining it without giving explicitly the polynomial (your Def 1). This is odd in the sense that all other NP-complete problems, like SAT, or in terms of graph problems, do not have such an implicit paramter in it. In these problems everything is at hand in the representation, which then admits a contructive way for reductions among these instances. $\endgroup$ – StefanH Feb 26 at 12:42
  • 1
    $\begingroup$ @StefanH Almost right, except we would want to query the oracle separately with $\phi_{accept}$ and $\phi_{out-of-bound}$. So we find out if it's possible to go out of bounds with some satisfying assignment, and we also find out if it's possible to accept with some satisfying assignment. $\endgroup$ – 6005 Feb 27 at 18:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.