0
$\begingroup$

I was reading the other day about this problem, refreshing it, and on a couple of places over the internet I read somebody explaining something in the line of '..does not matter as long as is polynomial, a N^20 or N^30 will do it, we know that maybe the solution does not make the problem tractable but if we can produce an algorithm having polynomial time complexity that will be good enough..."

My educated guess makes me think, that, if we can have a polynomial tractable algorithm , with today's computing resources, then that will be great, because we can use the solution, but looks like for P vs NP question as long as is polynomial that would be all.

How accurate are the comments I found on the internet?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
4
$\begingroup$

P vs NP is settled as soon as we find a $O(n^k)$ algorithm for an NP-complete problem (for any constant $k$) or show that no NP-complete problem has such an algorithm.

Whether or not $k$ is too big to yield a tractable algorithm is a different problem. Having a practical algorithm for, say, SAT, would indeed be very useful, many problems we currently solve heuristically (e.g. in chip design) could then be solved to optimality.

Improve this answer
$\endgroup$

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