[Solved]: Reduction examples from the strongly NPC problem 3-PARTITION

ignougroup
Problem Detail: 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.

Asked By : Vor

Answered By : hengxin

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/15015