We have had several questions about the relation of Cook and Karp reductions. It's clear that Cook reductions (polynomial-time Turing reductions) do not define the same notion of NP-completeness as Karp reductions (polynomial-time many-one reductions), which are usually used. In particular, Cook ...
A clarification: in the above implication "NPC" is relative to Turing or Karp reductions? (It is still an open problem if Turing-complete sets for NP are many-one complete, too)
@Vor "My" NPC denote the one defined by the "usual" definition which uses Karp reductions. (That is both a corollary from the linked questions we have and all I have found in literature myself.) Should I clarify that in the question?
Ok, but in this case suppose that $L_1 \in NPC_{T}$ (complete for NP under Turing reductions), then by definition, for all languages $L_2 \in NPC \subseteq NP$ we have $L_2 \leq_{T}^p L_1$; and if the above implication is true then $L_1 \in NPC$ and thus $NPC = NPC_{T}$ which is still an open question.
@Vor: I understand your deduction (which may be a valid answer to the question in itself) but I don't quite understand. scratch head Is there any way to use Cook reductions for proving (Karp-)NP-completeness? I'm asking because students cited a paper in exercises that (allegedly) used Cook reductions to show NP-completeness.
obviously every many-one reduction is a Turing reduction, so in a Turing reduction, if the oracle is called once, the returning value and the rest of the algorithm may "induce" a many-one reduction. And sometimes a Turing reduction is easily transformed to a many-one reduction. Can you provide a link to the paper?
... for example if you want to find a direct reduction from Hamiltonian cycle to Hamiltonian path, you must face with the problem that all nodes of the given graph can have degree $\geq 3$ and you don't know the two edges used by the cycle if it exists, so a quick Turing reduction is: pick a random node with degree $i$ as start node $s$, and run the Hamiltonian path algorithm $i$ times, picking as target node $t$ each node adjacent to $s$. To transform it into a many-one reduction it takes a little bit of work, but it is not so hard.
What is the problem that is proved to be NP-complete using a Turing reduction (Multiple alignment with SP-score or Tree alignment with given phylogeny) ?
Yes; They define X_{i,j} to be S plus two control strings whose length depends on i and j.
The (if) part of their proof supposes a suitable alignment in some X_{i,j}.
Consider the final sentence of their proof: "Therefore, by checking the value of an optimal alignment of X_{i,j}, i + j = m, we can answer if there is a supersequence i for X with length m in polynomial time." -- clearly Cook, not Karp.
@Vor I think you gave a sufficient answer in the comments: the statement I proposed implies an identity that is known to be open, so there is no simple proof available.
I think my main gap in intuition was that I only removed the NP vs co-NP issue from consideration; I did not think about NPC_T outside of both.
I'd still appreciate sufficient conditions on when Cook reductions are sufficient to show that a problem is in NPC_K, if there are any (known ones).
For 000 vs 00, an optimal alignment is 0 0 0 0 0 - Basically, any one deletion (gap in the lower string) is optimal. So you get once the gap cost.
They seem to be using Delta for gaps; so that would be score 1.
The score in Table 1 is not very meaningful in terms of defining closeness of strings; it's particular to solving Shortest Common Super Sequence.
The most common scores are (scaled) edit distance(s).
Basically, matches cost nothing and everything else the same. Some models assign higher penalty to mismatches than gaps, some the other way rounds -- it depends on what makes sense in the application. (E.g. in biology, is a missing character in RNA more significant than a wrong one?)
Discussion between Raphael and Vor
Discussion between Raphael and Vor