# Tag Info

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 ...

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

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 ...

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 ...

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 ...

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 ...

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

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