Problems harder than NP-Complete

Post by kevinwang » Wed, May 17, 2023, 4:41 AM UTC

eterevsky wrote: post #99

kevinwang wrote: post #93

Earlier quoted context omitted.

Consider a game like go, where board size is n. This means the game tree's branching factor is O(n). Let's say the game tree's depth is O(n) too. Then what is the size of the tree?

Under these conditions if you are doing a DFS over positions then you need to store O(n^2) positions in memory, considering that a position takes O(n) memory, you are using O(n^3) memory in total.

Post by kevinwang » Thu, May 25, 2023, 2:02 PM UTC

eterevsky wrote: post #102

kevinwang wrote: post #101

Earlier quoted context omitted.

If a tree's branching factor (i.e. the number of possible actions per turn) is N, and the depth of the tree (i.e. the length of the game) is N, the size of the tree is N^N, not N^2.

Yes. But you don't need to keep the whole tree in memory.