Ho un set di numeri S e voglio trovare il sottoinsieme più grande S 'tale che per ogni due elementi x, y in S' property(x, y) == True in_relation(x,y) == True .
Come ho potuto trovarlo? La bruteforcing è un'opzione, ok. Ma mi piacerebbe trovare qualcosa di più efficiente.
Ho paura che questo problema sia NP-completo, e quindi (probabilmente) può essere risolto solo da forzanti brute.
considera il problema IS (set indipendente), che è NP-completo. Dimostreremo che questo problema può essere ridotto al problema sopra descritto.
Sia G un grafo con Vertices set V. Costruiamo set S come numeri che enumerano i vertici di V, e costruisci la proprietà (x, y) come "xey non sono collegati da un bordo".
Questa build ha la complessità della n ^ 2 * complessità della proprietà (se non è polinomiale, il problema non è polinomiale per sua natura, altrimenti la build è polinomiale).
Ora, sia S 'il set di soluzioni trovato dall'algoritmo del problema. poiché l'insieme S e la proprietà sono costruiti esattamente su V e le proprietà no-edge, S 'può essere facilmente trasformato nella soluzione del problema IS.
Pertanto, il nostro problema risolve un problema NP-completo dopo una riduzione polinomiale e quindi è NP-completo stesso. fino ad oggi, non si conoscono soluzioni polinomiali (non brute-force) per problemi NP-completi.
Leggi altre domande sui tag algorithms