Exemplos de redução do forte problema de NPC 3-PARTITION

3-PARTITION é fortemente NP-completo , isto é, permanece NP-completo mesmo se a entrada for dada como unária.

Estou pesquisando dois ou três exemplos de problemas não numéricos (possivelmente bem conhecidos) que provaram ser NP-completos usando uma redução de 3-PARTITION (e a redução obviamente depende da fortemente np-completude). Gostaria das referências aos documentos originais.

Encontrei dois artigos, ambos sobre Tetris.

O primeiro é que Tetris é difícil, até aproximado por Erik D. Demaine et al. Ele usa o esquema de codificação unário para o problema de 3 partições e constrói uma redução polinomial:

o $a_i$'areia $T$são representados em unário, então o tamanho do jogo é polinomial. (do Teorema 3.2, página 9)

O outro é Tetris é Hard, Made Easy, de Ron Breukelaar et al. Ele também usa o problema unificado de 3 partições:

Observe que o painel é construtível em tempo polinomial (medido no tamanho da entrada), uma vez que as variáveis ​​na definição do problema podem ser dadas como unárias devido ao forte senso de completude do NP (Teorema 1). Sobre sua construtibilidade, consulte [4]. (da seção 2.3)

Eu não entrei nos dois artigos. Eles estão qualificados para o seu pedido de referências?

Edição: Encontrei recentemente outro exemplo de programação ideal de um sistema de trabalho com restrições de precedência ordenadas em dois processadores dedicados. Aqui está o artigo "Sobre a complexidade dos problemas de agendamento para máquinas paralelas / em pipeline" (IEEE Transactions on Computers 1989) .

O professor Erik Demaine contribuiu com a maravilhosa palestra (vídeo) de "Limites inferiores algorítmicos: diversão com provas de dureza (queda'14)" . Em particular, as aulas 2 e 3 são dedicadas às reduções (direta ou indiretamente) de$\textsf{3-Partition}$.

Por exemplo, a aula 2 trata de várias variantes de quebra-cabeças. Os resultados são coletados no artigo "Quebra-cabeças, Correspondência de Bordas e Embalagem de Polyomino: Conexões e Complexidade" . Seu resumo diz

Mostramos que os quebra-cabeças, quebra-cabeças correspondentes às bordas e quebra-cabeças de embalagem de polyomino são todos NP-completos. Além disso, mostramos equivalências diretas entre esses três tipos de quebra-cabeças: qualquer quebra-cabeça de um tipo pode ser convertido em um quebra-cabeça equivalente de qualquer outro tipo.

Provavelmente você já conheceu esses resultados e esta palestra em vídeo. No entanto, a maravilhosa palestra também pode ser útil para outras pessoas.