Complexidade do Problema de Alocação de Indicadores de Falha

  Falhas são inerentes aos sistemas de distribuição de energia, e os indicadores de falha (FIs) desempenham um papel crucial em sistemas inteligentes de distribuição com autocorreção, auxiliando na localização de defeitos. No entanto, a eficácia desses dispositivos depende de sua quantidade e de seu posicionamento adequado no sistema de distribuição, o que dá origem ao problema da Alocação de Indicadores de Falha.
  Trabalhos anteriores abordaram o problema com metaheurísticas, algoritmos genéticos ou formulações quadráticas, permanecendo em aberto a questão da existência de um algoritmo exato de tempo polinomial. Neste artigo, respondemos negativamente a essa questão, exceto se P = NP: apresentamos uma prova de NP-dificuldade para o problema, obtida por meio de uma redução a partir do problema SUBSET-SUM.