[Home] [Groups] - Message: [Prev in Group] [Next in Group]

nu.kanga.list.mud-dev

30742: Re: [MUD-Dev] Complexity and Accessibility

[Full Header] [Plain Text]
From: "Ola Fosheim Grøstad" <olag@ifi.uio.no>
Newsgroups: nu.kanga.list.mud-dev
Date: Tue, 31 Aug 2004 13:32:50 +0200
References: [1]
Organization: Kanga.Nu
Will Jennings <will.jennings@gmail.com> writes:

> degree that they are amenable to mathematical analysis, David
> Kennerly pointed out in a related thread that NP-hard
> (mathematical complexity) doesn't equal hard-for-people-to-play
> (overcomplication): it's easier to win at Minesweeper (which is
> NP-complete) than to beat the toughest FPS bot (which probably
> isn't solving too many NP-hard problems).

Can we please forget all that have been said about algorithmic
complexity... Anything finite or bounded by a constant can clearly
be solved in less than polynomial time, it is O(1).

Algorithmic complexity only tells you something about how the
complexity grows with the _scale_ of the problem.

Although there are some NP-hard problems that go a bit beyond that:
"Does God exist?".

  (Disclaimer: quite some times since I studied these things. Mostly
  useless. It's the computer science equivalent of pure
  mathematics.)

--
Ola - http://folk.uio.no/olag/
_______________________________________________
MUD-Dev mailing list
MUD-Dev@kanga.nu
https://www.kanga.nu/lists/listinfo/mud-dev