1
$\begingroup$

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.

  • 1
    I think your question will be better served if you ask something more specific.2012-09-26

1 Answers 1

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.