Re: what is NP-hard problem, esp in Commu?Re: NP-hard problem.# EE - 电子工程
r*r
1 楼
polynomial time means anything like n^k, where n in the input size of the
problem and k is a CONSTANT. So for example, if algorithms run in
O(n^2), O(n^100), O(n^100000), they are all polynomial time algorithms.
Exponential time, like 2^n is not a polynomial time, and anything bigger
than polynomial time is not practical in reality (actually when k > 3,
polynomail time algorithms isnot very useful already).
P is set of problems (not algorithms) that can be solved (rigous word is
decided) in poly
problem and k is a CONSTANT. So for example, if algorithms run in
O(n^2), O(n^100), O(n^100000), they are all polynomial time algorithms.
Exponential time, like 2^n is not a polynomial time, and anything bigger
than polynomial time is not practical in reality (actually when k > 3,
polynomail time algorithms isnot very useful already).
P is set of problems (not algorithms) that can be solved (rigous word is
decided) in poly
