Author: Dann Corbit
Date: 13:10:35 01/24/05
Go up one level in this thread
On January 24, 2005 at 14:21:03, Oreopoulos Kostas wrote:
>Sorry but if i am not mistaken ( and i am not) defining a problem as Hard NP is
>not a matter of finite or infinite space. Its whether the algorithm is O(n) or
>O(2^n). The main difference i see from a typical trav salesman prob is that in
>chess we have evaluation functions, which as a result lower the branching factor
>of the space. The question of NP hard is if we can make the evaluation functions
>so efficient that the Best move question breaks down to an O(n) algorithm.
>
>It is obvious that i dont mean about searching the space. THis is the obvious
>solution to every [at first sight] NP problem.
If a problem is NP then it cannot be solved in polynomial time. Simple as that.
NP means (N)on-(P)olynomial.
O(n) is also polynomial time and (in fact) is linear.
O(n*log(N)) and O(n^2) and O(n^3) are all polynomial time.
So if a problem is polynomial time, then we can solve it in O(2^n) {where n is a
constant as you mention}
However, if a problem is non-polynomial in time, then no matter what fixed
polynomial we chose, if we produce a big enough data set, then the solution will
take longer than the time predicted by any polynomial.
So exponential time is NP. And factorial time is NP.
O(n^10000) is polynomial time, but pragmatically insoluable except for n=1.
It takes a really hard problem to be NP in time. Lots of them are graph
problems like TSP.
You could also have problems that are NP but easy to solve (e.g. something
proportional to e^1.000000000000000001) and polynomial problems that are
intractable like our n^10000 problem, above.
You can also have problems that are O(1) in calculation but O(exp(n)) in space
and these are also intractible [in general].
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.