Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Edge Matching with Inequalities, Triangles, Unknown Shape, and Two
  Players   We analyze the computational complexity of several new variants of
edge-matching puzzles. First we analyze inequality (instead of equality)
constraints between adjacent tiles, proving the problem NP-complete for strict
inequalities but polynomial for nonstrict inequalities. Second we analyze three
types of triangular edge matching, of which one is polynomial and the other two
are NP-complete; all three are #P-complete. Third we analyze the case where no
target shape is specified, and we merely want to place the (square) tiles so
that edges match (exactly); this problem is NP-complete. Fourth we consider
four 2-player games based on $1 \times n$ edge matching, all four of which are
PSPACE-complete. Most of our NP-hardness reductions are parsimonious, newly
proving #P and ASP-completeness for, e.g., $1 \times n$ edge matching.

9
The categories of this paper are: nlin
32
The categories of this paper are: atom-ph
8
The categories of this paper are: hep-ex
25
The categories of this paper are: patt-sol
30
The categories of this paper are: q-alg
6
The categories of this paper are: astro-ph
15
The categories of this paper are: nucl-ex
19
The categories of this paper are: eess
35
The categories of this paper are: mtrl-th
0
The categories of this paper are: hep-ph
24
The categories of this paper are: dg-ga
5
The categories of this paper are: gr-qc
2
The categories of this paper are: math
26
The categories of this paper are: bayes-an
34
The categories of this paper are: chem-ph
14
The categories of this paper are: math-ph