Computer Chess Club Archives

Search

Messages

Subject: Re: is Chess a Hard NP? - No!

Author: Oreopoulos Kostas

Date: 11:21:03 01/24/05

Go up one level in this thread

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.

• Re: is Chess a Hard NP? - No! Dann Corbit 13:10:35 01/24/05
  • Re: is Chess a Hard NP? - No! Dann Corbit 13:14:18 01/24/05
    • Re: is Chess a Hard NP? - No! Robert Hyatt 08:45:09 01/25/05
      • The complexity of solving chess is O(1) Omid David Tabibi 09:59:28 01/25/05
        • Re: The complexity of solving chess is O(1) Robert Hyatt 10:41:49 01/25/05

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.