All Questions
Tagged with combinatorial-game-theory computational-complexity
7 questions
15
votes
0
answers
488
views
Does the Angel have to be really smart?
My question is about the computational complexity of the Angel's strategy in the Angels and Devils game, tl;dr does the Angel have a polynomial time strategy.
I'm a big Conway fan, so as you can ...
- 6,652
13
votes
1
answer
399
views
Two-player independent set game
Let $G = (V, E)$ be a finite graph, and $S \subseteq V$ initially be an empty set. Alice and Bob play a game, making moves in turns starting with Alice. A move consists of choosing a vertex $v \in V \...
- 5,590
6
votes
1
answer
173
views
What is the minimum worst-case length of an element removal game?
A game is played as follows. There is a set $X = \{1, \ldots, n\}$. Player 1 is trying to find a "locally minimal subset" $M \subseteq X$ - that is, player 2 has said that $M$ is good, and also that ...
- 1,331
5
votes
1
answer
780
views
Algorithmic war
No, not the war on drugs, but the game of War considered in
Does War have infinite expected length?
As noted in that discussion, the game of war can go on forever, but my question is: can it be ...
- 96.4k
2
votes
3
answers
462
views
A faster way to spoil an injection?
Ultimately this is about how primes jump. I will abstract the situation somewhat as there may be related applications which do not spring to my mind.
I want to find small spoilers to Hall's Marriage ...
- 13k
1
vote
1
answer
151
views
Complexity of games with graph classes
Let $\mathfrak{G}$ be the class of all finite directed and undirected graphs. Let $A,B\subseteq \mathfrak{G} $, $A$ and $B$ are closed under graph isomorphisms, and $A \cap B = \varnothing$. Consider ...
- 107
1
vote
0
answers
102
views
Fast algorithm to compute nimber product
It is known that nimbers (Grundy numbers) below $2^{2^n}$ form a field with the nim addition $\oplus$ and the nim product $\cdot$.
Generally, one can develop an algorithm to compute the product of two ...
- 1,171