Author: Omid David Tabibi
Date: 09:59:28 01/25/05
Go up one level in this thread
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).
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.