Perguntas com a marcação «np-hardness»

10
Dureza de uma subcaixa de Set Cover

Quão difícil é o problema Set Cover se o número de elementos estiver delimitado por alguma função (por exemplo, ) em que é o tamanho da instância do problema. Formalmente,nlognlog⁡n\log nnnn Deixe e que e . Quão difícil é decidir o seguinte problemaF = { S 1 , ⋯ , S n } S i ⊆ U m = O ( log n...