Author: Dann Corbit
Date: 13:14:18 01/24/05
Go up one level in this thread
On January 24, 2005 at 16:10:35, Dann Corbit wrote:
>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].
I went and did a web search, and found that my definition for NP was wrong.
NP means verified in polynomial time, when used in the classical sense. The
term Non-polynomial is not abbreviated as NP.
http://en.wikipedia.org/wiki/Complexity_classes_P_and_NP
My description of polynomial and non-polynomial is correct (I think) but my
abbreviation NP is not correct.
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.