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.
|
|
