For example in this post they discuss how to construct a reduction between problems to show that one probleme is NP-Hard: Post

I am searching for a scientific paper to cite where it is written, that this is a valid method.

Does anybody knows one?

  • 3
    $\begingroup$ Polynomial-time reduction on Wikipedia has a lot of references that could be helpful. Indeed, this is standard textbook material. $\endgroup$ – Juho Jan 12 at 19:33
  • 1
    $\begingroup$ Try Karp’s classic paper On the reducibility of combinatorial problems. You can also cite relevant textbooks. $\endgroup$ – Yuval Filmus Jan 12 at 21:19
  • $\begingroup$ Another relevant result is Cook-Levin teorem (Cook's paper should include some useful citations). $\endgroup$ – narek Bojikian Jan 13 at 6:59

If I may make an assumption, you want such a reference to be able to put it in one of your works, right ? I don't why you would wanna do that as if you have a problem A, reducting a NP Hard problem to problem A quite clearly shows that A is NP Hard. No one bothers proving it as it's such a straightforward and fundamental result. If you need to prove it for some reason you can do it in two lines. If you still want a reference for a reader to read about NP in general then just quote Arora and Barak's book on complexity theory.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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