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.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
closed as not a real question by Austin Mohr, William, tomasz, Norbert, Asaf Karagila Oct 6 '12 at 10:02
It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.
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.