Computer Chess Club Archives

Search

Terms

Messages

Subject: Re: is Chess a Hard NP?

Author: Robert Hyatt

Date: 07:20:09 01/20/05

On January 20, 2005 at 06:43:18, Oreopoulos Kostas wrote:

>Is there a proof the Chess ia actually an Hard NP problem?


yes, it is exponential, which is non-polynomial.  Tree size = W ^ D.  That puts
it out of any sort of polynomial representation instantly...

Re: is Chess a Hard NP? Robert Hyatt 07:40:11 01/20/05
- Re: is Chess a Hard NP? Russell Reagan 19:44:13 01/20/05
  - Re: is Chess a Hard NP? Dann Corbit 20:18:01 01/20/05
    - Re: is Chess a Hard NP? Russell Reagan 00:50:37 01/21/05
      - Re: is Chess a Hard NP? José Carlos 04:37:46 01/21/05
      - Re: is Chess a Hard NP? Dann Corbit 01:27:23 01/21/05
        
        Re: is Chess a Hard NP? Mark Rawlings 08:34:21 01/21/05
        
        Re: is Chess a Hard NP? Uri Blass 02:51:32 01/21/05
        
        Re: is Chess a Hard NP? Oreopoulos Kostas 03:06:51 01/21/05
        
        Re: is Chess a Hard NP? Robert Hyatt 09:07:28 01/22/05
        
        Re: is Chess a Hard NP? Dann Corbit 13:56:15 01/21/05
        
        Re: is Chess a Hard NP? Robert Hyatt 09:09:57 01/22/05

This page took 0.01 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.