Definition of a 'simple' rules in a combinatorial game

44 Views Asked by At

I have looked on the internet for this for some time. Unfortunately, when I make a search that includes the words "definition" and "simple", the search engine is certain I am looking for a simple definition rather than a definition of simple.

Apparently Elwyn Berlekamp asked if:

there is a game that has simple, playable rules, an intricate explicit solution, and is provably NP or harder.

Note I have left words in bold that were bold in the source of the quote (a list of open problems in combinatorial game theory).

So what does simple mean in this context?

1

There are 1 best solutions below

0
On

I agree with the comments that "simple" probably doesn't refer to a precisely defined technical notion - certainly not a standard one.

I think "simple" is intended to mean something like "can be described without to much text, implemented by a human easily, and crucially, doesn't explicitly encode any computationally hard problems". If you make the determination of whether a move is legal require solving an $\mathsf{NP}$-hard problem, that defeats the point.


As an aside, I'm curious/concerned about the "explicit solution" part. Presumably "write out the game tree (easy to do since the rules are simple) and mark every position as a win for the appropriate player" doesn't count as an explicit solution. But then I'd want to define "explicit solution" as something that doesn't take computational power to work through, which seems at odds with the solution being $\mathsf{NP}$-hard.