Author: Ricardo Gibert
Date: 10:08:18 05/09/01
Go up one level in this thread
On May 09, 2001 at 11:45:27, Robert Hyatt wrote: >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. You're confusing "infinity" with unbounded. I'm not. It's silly to talk about asymptotic behavior as being a function of n when n is constant. If n is constant, then f(n) is constant. Running time (or whatever) is then bounded by a constant c. That's O(1). If n is unbounded (that does not mean infinity, please), then it makes sense to speak of asymptotic behavior as being bounded by a function of n i.e. f(n). In a nutshell, if n is unbounded, then we compare O(f(n)) with O(1), then it is *not* the case that there exists a c sth f(n) = c*(1). If n is bounded, then such a constant c does exist for f(n) = c*(1). Normally n is unbounded such as in the traveling salesman problem or sorting or searching, etc. In chess, the size of the problem is bounded (fixed, constant, etc). The size of the board is fixed, otherewise it ceases being chess. If the size of the board were unbounded, then what you are saying would make sense, but that is *not* the case. The bottom line is only a finite number of positions need to be considered to solve chess. That number may be huge, but it is finite all the same. The time it takes to solve chess is O(1), since there *does* exist a constant c sth the number of steps needed to solve it is bounded by c*(1). In the traveling salesman problem, f(n) is NP rather than P, since there does *not* exist a constant c sth f(n) = c*P, since n is unbounded. It essential to understand the terms bounded, unbounded and infinity in their proper context.
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.