I understand karp reduction can be used to change a problem and calls an oracle. But what is the oracle? How is it used? What are the details of a karp reduction? What is it that is reduced? I found the material to read about it somewhat inaccessible.
How does karp reduction work?
1
$\begingroup$
algorithms
-
1I think your question will be better served if you ask something more specific. – 2012-09-26
1 Answers
1
I found this material, there 'instance' means input word, I guess.
This is the main method to prove complexity problems. For example, the Hamilton cycle problem is NP-complete, meaning that 'if there is an oracle for Positive Answer', then the answer is 'verified' in polynomial time (of the size of the input). Now the input is a $G$ graph, and the oracle can be the Hamilton cycle itself. It is also NP-complete, meaning that any other NP problem can be reducted to this Hamilton cycle problem.
See also these, all problems reducted one to the other.