How do you show that MAX-CLIQUE = {<G,k> | the largest clique in G is
of size exactly k} is DP-complete?
Z = {<G1,k1,G2,k2>, G1 has a k1-clique and G2 doesn't have a
k2-clique} is DP-complete
It is easy to show a polynomial time Turing reduction from Z (binary
search), but not a many-one mapping reduction necessary(as far as I
know) to prove DP-completeness.
I dont know how to find a many-one reduction. |
Request for Question Clarification by
mathtalk-ga
on
08 Aug 2004 14:34 PDT
Hi, nr9-ga:
Don't you want the reduction to go in the other direction? That is,
if you ask me about Z, would I be able to answer with a single inquiry
to MAX-CLIQUE?
Not that I see how to arrange that, but my intuition is that:
Z is DP-complete ==> MAX-CLIQUE is DP-complete
must depend on knowing Z is many-one reducible to MAX-CLIQUE, not
MAX-CLIQUE from Z as your comment about binary search seems to
suggest.
regards, mathtalk-ga
|
