Author: Robert Hyatt
Date: 10:41:49 01/25/05
Go up one level in this thread
On January 25, 2005 at 12:59:28, Omid David Tabibi wrote:
>On January 25, 2005 at 11:45:09, Robert Hyatt wrote:
>
>>On January 24, 2005 at 16:14:18, Dann Corbit wrote:
>>
>>>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.
>>
>>
>>NP means "nondeterministic polynomial". For example, you write an automaton to
>>recognize some "thing". At each decision point you can spawn new threads, and
>>each thread is guaranteed to complete in polynomial time, even though there
>>might be a _bunch_ of such threads.
>>
>>A palindrom recognizer is an easy example. You read in characters and at some
>>point you assume you reach the middle of the string and now start matching with
>>what you read in beyond that point. The non-deterministic solution is that you
>>read in a character, and spawn a new thread that assumes this is the midpoint of
>>the string, and starts reading in additional characters looking for the reverse
>>match. If you match every character, and run out after the last match, this is
>>a palindrome. Otherwise this thread says "no" and is done. The other thread
>>reads in the second character, and spawns a new thread to start testing here.
>>Repeat for every character read. If any one of the threads says "yes" then the
>>input is a palindrome. If all say no, then it is not. Should all threads be
>>guaranteed to complete in polynomial time, then you have a workable solution so
>>long as the number of threads can be managed.
>>
>>It is impossible to divide up a tree that grows exponentially, into sub-pieces
>>that only grow polynomially. IE for any tree to depth D, we need to reduce that
>>into some number of trees that can be represented by a polynomial complexity.
>>Can't be done unless the base properties of the tree are modified, such as
>>reducing the branching factor to 1.0 somehow...
>
>
>A friend of mine once told me: "why do you make such a fuss about
>computer-chess, it takes only O(1) to solve it." And he was right of course, as
>the number of possibilities in chess is bounded by a constant (large as it might
>be).
That's a famous ridiculous argument. One day it might be O(1). Today it is
O(W^D), and it will remain so until W^D reaches the size of the max tree size
possible.
Best response is that yes, the game is finite, but the tree grows exponentially
until that unreachable search space has been traversed...
Back to the regularly scheduled flame wars now. :)
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.