# Tag Info

Accepted

### Among an infinite variety of n x n board games, why are some interesting?

I've spent a lot of time on problems related to the computational complexity of (puzzle) games and I think there are many orthogonal aspects that can make a two-players or a one-player (puzzle) game ...

### Can generalized twenty questions be solved by a greedy algorithm?

Your question is not very different from set cover (it would be exactly set cover if you stopped as soon as you found a set containing $x$ rather than keeping going until you have determined $x$) and ...
• 51.1k
Accepted

### Can generalized twenty questions be solved by a greedy algorithm?

No. There's a huge literature on the topic, called combinatorial search theory, you can read more about these types of questions there. The simplest example that I could think of is the following. ...
• 14k

### How much information does it take to specify, not each member of a group, but any one member?

This answer continues Peter's. It assumes Peter's interpretation of the problem and verifies that with that interpretation the function $f(S)=\min S$ is optimal, as Peter suggested. Here's the ...
• 10.8k
Accepted

### Winning strategy in the game of triplets

This isn't a complete proof, but here's some justification for why known conjectures imply that the game may be computationally hard to solve. Namely, I'm going to argue that finding the correct first ...
• 1,642

### How hard is Hex from a symmetric position?

Finding a winning move in symmetric positions in Hex is PSPACE-complete First, let's define our problem, and call it SYMHEXMOVE: Take as an input: a symmetric Hex position Output: any move which is ...
• 156

### The logic in derivation of virtual welfare

I think I've gotten part of the answer. The above statement actually says that for any truthful mechanism, the expected profit is equal to its expected virtual surplus. If we are searching for ...
• 191

### Implementation of surreal numbers for games

Here is an implementation of Surreal Numbers in a relatively new language, Julia. https://github.com/mroughan/SurrealNumbers.jl Described at https://www.sciencedirect.com/science/article/pii/...
• 21

### Is there a natural problem on the naturals that is NP-complete?

Our FOCS'17 paper on the Short Presburger Arithmetic is an example of a "natural" problem which is NP-c, and uses a constant number $C$ of integers in the input, say $C< 220$. It is different from ...
• 812
the calculation of $\mathcal{SW}_{-D_i}$ and $\mathcal{SW}_{-C_i^\mathcal{K}}$ is incorrect. There are still $\mathcal{K}$ items to be allocated in both allocations, so for node $D$, the first is 20+...