Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

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 think your question will be better served if you ask something more specific. – Austin Mohr Sep 26 '12 at 22:19
up vote 1 down vote accepted

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.

share|cite|improve this answer "if the answer is Yes to the decision problem, then there is an algorithm" and we can verify the solution in polynomial time. Thank you for the information. – Programmer 400 Sep 27 '12 at 7:24

Not the answer you're looking for? Browse other questions tagged or ask your own question.