I have never been very clear on this concept. Please help:
At the end of the day, we should want to identify useful problems for which we don't have polynomial solution so far and only have exponential solutions.We want to keep finding if we can find a polynomial solution to these problems and the use of reductions is only to be able to identify new only exponential solvable problems with help of existing known exponential problems.??
Why is concept of determinism and non determinism brought into this whole concept of exponential and polynomial solvable problems?? How is this notion useful?
What do we call the problems for which we have only exponential solution so far, but we haven't been able to find reduction to a known NP - hard/complete problems..??
Thanks,