 3:15 PM
2  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. 3:15 PM
The paper is On the Complexity of Multiple Sequence Alignment by L. Wang and T. Jiang (1994). The problem is NP-complete, but they use a Turing reduction. 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) ? @Vor The former. They show some other completeness for the latter.
The proof starts on page 3.
Or 339, if you follow the printed numbers. Do Xi,j correspond to multiple "multiple sequence alignment with SP-score" instances? 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). 3:33 PM
Reading the proof it seems that there is another imprecision: the SP scheme is part of the input and should be "listed" in the "INSTANCE" section
I'm trying to grasp it ... why 0-0 scores 2 ? (the two symbols are the same and they are aligned so it should be 0)
(I think that a single call to the oracle should be a sufficient condition)
Now I see that the score scheme is fixed before "SP score" (... the reference to the table should have been placed before ... :-S ) @Vor I think the scoring is globally fixed, as is the alphabet.
They may be imprecise, but that's not a big issue.
As far as I can tell. 3:50 PM
Just for curiosity, what are the minimum alignments values for the pair of sequences: 000,00 and for the sequences: 010,010 using the SP-scheme? Ehhh.
I don't have that one in mind.
The scoring, that is. I'm only trying to understand the scoring system :-) :-) If X = { 000,00 }, what is its score? And if X = { 010, 010 }
Sorry, I must leave 4:12 PM
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?)