Author: Robert Hyatt
Date: 08:45:27 05/09/01
Go up one level in this thread
On May 09, 2001 at 10:12:30, Ricardo Gibert wrote: >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). In complexity theory that is _not_ an issue. The number of memory references has nothing to do with O(N^2). In this case, the complexity simply says that the solution time varies with the _square_ of the number of inputs. It doesn't matter whether you use a 1 bit memory word or a 128 bit memory word. And clearly for chess, the complexity varies as an exponential function of the search depth. As I have said repeatedly, _no_ algorithm terminates with infinite input so that doesn't have anything to do with complexity here at all. Nor does the number of "steps" required to do a single task affect it. It is all about the number of input values and a function that predicts running time based on that number. Otherwise we would _never_ see O(Nlog(N)) vs O(N^2) when talking about sort. They would be the same since we obviously can't sort an infinite number of items, ever.
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.