34

Based on the discussion, I’ll repost this as an answer. As proved by Manders and Adleman, the following problem is NP-complete: given natural numbers $a,b,c$, determine whether there exists a natural number $x\le c$ such that $x^2\equiv a\pmod b$. The problem can be equivalently stated as follows: given $b,c\in\mathbb N$, determine whether the quadratic $x^...


19

A family of bitvectors is the class of solutions to a 2-SAT problem if and only if it has the median property: if you apply the bitwise majority function to any three solutions you get another solution. See e.g. https://en.wikipedia.org/wiki/Median_graph#2-satisfiability and its references. So if you can find three solutions for which this is not true, then ...


18

This problem has a variation with a single integer input: Does $n$ have a divisor strictly in between its two largest prime factors? The idea is to use the same randomized reduction from subset sum described in the top answer to the linked question, but with the target range encoded as the largest two primes instead of given separately. The definition ...


12

The best known example is probably checkers (also known as draughts), which has been solved recently in 2007 (the game is a draw). Other examples are listed in the Wikipedia page on solved games; notable among them are connect four and nine men's morris. Additionally, several chess endgames have been solved. This perhaps doesn't seem like an answer to your ...


11

I think Kaveh's comment is the correct answer: applications? We don't need no applications. But despite all that, combinatorial game theory does appear to have some applications in error correcting codes. See Conway and Sloane, "Lexicographic codes: Error-correcting codes from game theory", IEEE Trans. Inf. Th. 1986. More simply, if you are willing to ...


10

Here's a $\text{NEXP}$-complete problem with a single natural number as the input. The problem is about tiling an $n \times n$ grid with a fixed set of tiles and constraints on adjacent tiles and tiles on the boundary. All of this is part of the specification of the problem; it is not part of the input. The input is only the number $n$. The problem is $\...


10

Let $P(x_1,\ldots,x_n)$ be a property on $n$ variables. Suppose that there is a 2CNF formula $\varphi(x_1,\ldots,x_n,y_1,\ldots,y_m)$ such that $$P(x_1,\ldots,x_n) \Leftrightarrow \exists y_1 \cdots \exists y_m \varphi(x_1,\ldots,x_n,y_1,\ldots,y_m).$$ We claim that $\varphi$ is equivalent to a 2CNF formula $\psi$ involving only $x_1,\ldots,x_n$. To prove ...


10

Undirected (Vertex) Geography is in P. In particular, the game on graph $G$ with starting vertex $v$ is a win for player 1 if and only if every maximum matching of $G$ uses the vertex $v$. This can be checked in polynomial time. The above is Theorem 1.1 from the paper "Undirected Edge Geography", by Fraenkel, Scheinerman and Ullman, Theoretical Computer ...


8

I don't have an answer to your question of whether the theory of Conway games has been used in building game-playing programs, but still you might be interested in the Combinatorial Game Suite, "an open-source program to aid research in combinatorial game theory" (which I first learned about here). It includes an implementation of various standard ...


8

See Wolfe and Berlekamp -- Mathematical Go. Using Conway's theory of games, they show how to analyze certain kinds of Go endgames. Their solutions turn out to be measurably better than the solutions given by top Go players. (Not quite an answer to your problem, as those latter solutions were probably never claimed to be optimal.)


7

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 attractive and fun: simple rules; simple "physical elements" needed to play it (e.g. a bounch of stones like in Mancala) ... clearly nowadays this condition is ...


6

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 it's easy to adapt bad instances to set cover to show that the greedy algorithm can ask more questions than optimal by a logarithmic factor. To see this, ...


6

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. Suppose that you want to find an edge of a graph, and you can ask whether a given vertex is incident to the hidden edge, or not. Now take the following bipartite ...


5

(a) Addition and multiplication are both in $L$: http://people.clarkson.edu/~alexis/PCMI/Notes/lectureB02.pdf $-$ so counting in $L$ should be possible. (Yes, I know that addition, multiplication and counting compute functions, but it's easy to convert them to decision versions of their respective problems.) (b) Since $L \subseteq NL$, and 2-CNF is ...


4

First of all, note that it is always beneficiary to start the game with asking each citizen their role if we are looking for a deterministic winning strategy for Town. This is because if no matter what the Mafiosi declare themselves the Town wins, then it is obviously no harm to ask. And if the Mafiosi can declare themselves something and win in that case, ...


3

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 move is already probably tricky. As a first step, we argue that the triplets game is harder (in the appropriate sense) than the $\textrm{Denser Induced ...


3

on some search there do not seem to be much published general implementations of surreal numbers. heres an implementation of surreal numbers in coq. Surreal numbers in coq / Mamane, TYPES'04 Proceedings of the 2004 international conference on Types for Proofs and Programs Surreal Numbers form a totally ordered (commutative) Field, containing copies of ...


3

I was able to find an application of combinatorial game theory in cryptography. See the link here


2

I post an update as a self-answer only to keep it distinct from the question (which is still open). As shown in the comments (thanks to Tsuyoshi Ito) the problem is polynomial-time solvable for paths: $Win(P_n) = 1$ iif $(n \bmod 34) \in \{3,7,23,27\}$ Starting from 0, the (calculated) sequence of the nim values is periodic: 0,1,1,0,2,1,3,0,1,1,3,2,2,3,4,...


2

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 Manders-Adleman in that the constraints are all inequalities. See Gil Kalai's blog post for some background.


2

I think that using one of the time-bounded variants of Kolmogorov complexity you can build a problem that uses only the binary representation of a number and (I think) is unlikely to be in $\mathsf{P}$; informally it is a decidable version of the problem "Is $n$ compressible?": Problem: Given $n$, does a Turing machine $M$ exist such that $|M| < l$ and $...


2

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/S2352711018302152


2

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 truthful mechanisms only, then by the Myerson's Lemma the payment rule must be in that form.


1

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+19+17+11+10 and the second is 20+19+17+14+11. So D's payment is 10. p.s. there is a typo in one of the constraints for the two allocations, which is updated in ...


1

Combinatorial game theory and topics thereof has received a lot of attention in modelling and verification of reactive systems. I would draw your attention to this nice reference for more information.


1

It is not properly a "game strategy", however in 2010 Tomas Rokicki, Herbert Kociemba, Morley Davidson, and John Dethridge found that all Rubik's cube positions can be solved with a maximum of 20 face turns using a computer-assisted proof [1] ... a nice result. The annotated source code is available at http://cube20.org/src/. The average number of moves ...


1

Chess endgame techniques have been greatly enhanced by the advent of endgame tablebases. Endgame tablebases are lookup tables that solve chess when there are no more than (currently) seven pieces on the board. Here is an online tablebase I've used in the past that works for up to six pieces. Algorithmically, these tablebases are not very interesting; they ...


1

How about the PARTITION problem?


1

The game you've described looks a lot like the game of k Cops and 1 Robber, as described in this article by Clarke and Macgillivray : http://www.sciencedirect.com/science/article/pii/S0012365X12000064. Basically, it is played by placing k cops and a robber on the vertices of a graph and asking the cops to catch the robber by moving along the edges. The ...


Only top voted, non community-wiki answers of a minimum length are eligible