Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
3-PARTITION is strongly NP-complete, i.e. it remains NP-complete even if the input is given in unary.
I'm searching two or three examples of (possibly well-known) non-numeric problems that have been proved to be NP-complete using a reduction from 3-PARTITION (and the reduction obviously relies on the strongly np-completeness). I would like the references to the original papers.
I found two articles, both on Tetris.
The first one is Tetris is Hard, Even to Approximate by Erik D. Demaine et al. It uses the unary encoding scheme for 3-Partition problem and constructs a polynomial reduction:
The $a_i$'s and $T$ are represented in unary, so the size of the game is polynomial. (from Theorem 3.2, page 9)
The other one is Tetris is Hard, Made Easy by Ron Breukelaar et al. It also uses the unary 3-Partition problem:
Note that the board is constructable in polynomial time (measured in the input size), since the variables in the problem definition may be given in unary due to the strong sense of NP-completeness (Theorem 1). On its constructibility, consult [4]. (from section 2.3)
I did not go into the two articles. Are them qualified to your references request?
EDIT: I recently found another example of optimal scheduling of a job system with ordered precedence constraints on two dedicated processors. Here is the paper "On the Complexity of Scheduling Problems for Parallel/Pipelined Machines" (IEEE Transactions on Computers 1989).
Prof. Erik Demaine has contributed the wonderful (video) lecture of "Algorithmic Lower Bounds: Fun with Hardness Proofs (Fall'14)". In particular, lectures 2 and 3 are devoted to the reductions (directly or indirectly) from $\textsf{3-Partition}$.
For example, Lecture 2 is concerned with several variants of Jigsaw puzzles. The results are collected in the paper "Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and Complexity". Its abstract says
We show that jigsaw puzzles, edge-matching puzzles, and polyomino packing puzzles are all NP-complete. Furthermore, we show direct equivalences between these three types of puzzles: any puzzle of one type can be converted into an equivalent puzzle of any other type.
Most probably you have known these results and this video lecture. However the wonderful lecture may be also useful for other people.
