Author: Ricardo Gibert
Date: 07:12:30 05/09/01
Go up one level in this thread
On May 09, 2001 at 02:00:25, Dann Corbit wrote: >For those of you who don't want to perform your own web search, just choose one >of these: > >http://hissa.nist.gov/dads/HTML/bigOnotation.html >http://bio5495.wustl.edu/textbook-html/node15.html >http://umastr.math.umass.edu/~holden/Math136-99_projects/Amstutz-OBoyle-Petravage/big-o.html >http://www.eecs.harvard.edu/~ellard/Q-97/HTML/root/node8.html >http://classes.monterey.edu/CST/CST338-01/world/BigO.html >http://shalim.csustan.edu/~john/Classes/CS3100_DataStructures/Previous_Semesters/1999_04_Fall/Examples/big-O > >CS:201, FCOL! Big-O notation is used to describe asymtotic behavior. It commonly used to describe the "running time" of an algorithm. If an algorithm is O(f(n)), n is understood to be a finite, but *unbounded*. (For some reason, "unbounded" gets confused with infinity. This is an error, but let's not get into that. It isn't relevant here) In chess, n in is bounded. This is a critical distinction, that means chess is *not* NP. If we were to allow the size of the chessboard to expand, then the number of steps in its solution would be NP (extremely likely, but not certain!) The mini-max algorithm is provably NP, since in its general formulation, n is unbounded, but in its application to chess n is bounded to a constant and so the number of steps to execute the alogorithm is also bounded to a constant. In some other games, the size of the game is not bounded as it is in chess, so their solution may not be bounded by a constant. In a game like Nim, where the size of the game is unbounded. Despite this, there is a known method to solve it that is O(1). (Actually, it dependes on how you count a "step", so O(log(n)) for instance is another defensible answer). Chess does not qualify as NP for a semantic reason. If the size of the board is not bounded to 8x8 = 64 squares, then it is not chess! In computer since, the use of Big-O is often used "fast and loose". For instance, the running time of bubble sort is descibed as O(n^2). This is not accurate. The number of steps is O(n^2), but some of the steps do not execute in constant time. The time it takes to perform a memory move of or comparison of an item of data depends on the size of the data element. If the keys to be sorted are distinct, then the lower bound on the size of the data element is proportional to log(n). There are other typical examples in other areas of computer science too (e.g. algorithms dealing with matrices).
This page took 0.02 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.