r********r 发帖数: 11248 | 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 | r********r 发帖数: 11248 | 2 Currently the biggest problem of computer science is: if N=NP or if N is a
proper subset of NP.
Give you an example which is not a NP problem.
{: program never terminate} and {: this guy will never die}.
Even you know the solution, you cannot vertify (confirm) it in polynomial
time.
【在 r********r 的大作中提到】 : 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
| c****g 发帖数: 7 | 3 Good Terminologies. let me explain them more clearly..
NP-Problem
A problem is assigned to the NP (nondeterministic Polynomial time) class if it
is solvable in polynomial time by a nondeterministic Turing Machine. (A
nondeterministic Turing Machine is a ``parallel'' Turing Machine which can
take many computational paths simultaneously, with the restriction that the
parallel Turing machines cannot communicate.) A P-Problem (whose solution time
is bounded by a polynomial) is always also NP. If a s
【在 r********r 的大作中提到】 : Currently the biggest problem of computer science is: if N=NP or if N is a : proper subset of NP. : Give you an example which is not a NP problem. : {: program never terminate} and {: this guy will never die}. : Even you know the solution, you cannot vertify (confirm) it in polynomial : time.
|
|