All Questions
2 questions
16
votes
2
answers
2k
views
What is so fundamental about polynomial functions that they are used to demarcate the Hardness boundary in NP complexity classes?
This question has been bugging me ever since I first came across the concept of NP, NP-Complete, and NP-Hard a few years back: what is so fundamental about the polynomial functions that they are used ...
D.W.♦
- 166k
6
votes
1
answer
166
views
Is there such a notion as "effectively computable reductions" or would this be not useful
Most reductions for NP-hardness proofs I encountered are effective in the sense that given an instance of our hard problem, they give a polynomial time algorithm for our problem under question by ...
- 7,248