Complexidade do Positional Knapsack Problem - Pedrosa, Lehilton L. C.; Silva, Mauro R. C.; Schouery, Rafael C. S. (Anais do Encontro de Teoria da Computação (ETC), 2022)
Neste resumo, apresentamos o Positional Knapsack Problem (PKP) e demonstramos que ele é NP-difícil. O PKP é uma variante do Knapsack Problem (KP) em que o valor de um item varia linearmente de acordo com a posição em que ele é adicionado. Essa mudança na valoração adiciona diversas propriedades não intuitivas ao problema que não valem para o KP e, de fato, o PKP não é uma generalização do KP. Para demonstrar a NP- dificuldade, reduzimos uma variante do Partition Problem a uma instância de PKP cuidadosamente construída, de forma a recuperar algumas propriedades normalmente esperadas para variantes do KP.