Tell me more ×
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.
up vote 1 down vote favorite

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

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, see the FAQ.

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. – Nick Rosencrantz Sep 27 '12 at 7:24

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