7
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Nice! I found other examples like the Isomorphic Implication Problem, but they are not so popular ... $\endgroup$ – Vor Oct 13 '13 at 9:59
  • 1
    $\begingroup$ @Vor Another problem found recently is added. $\endgroup$ – hengxin Mar 8 '14 at 12:19
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.