Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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.

1  
I think your question will be better served if you ask something more specific. –  Austin Mohr Sep 26 '12 at 22:19
add comment

1 Answer

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|improve this answer
    
Aha...like "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. –  909 Niklas Sep 27 '12 at 7:24
add comment

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