Author: Robert Hyatt
Date: 08:45:09 01/25/05
Go up one level in this thread
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...
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.