I have a set of numbers S and I want to find the largest subset S’ such that for any two elements x,y in S’ property(x, y) == Truein_relation(x,y) == True.
How could I find it? Bruteforcing is an option, ok. But I’d like to find something more efficient.
4
I’m afraid thas this problem is NP-complete, and hence can (probably) only be solved by brute-forcing.
consider the IS (independent set) problem, which is NP-complete. We shall prove that this problem can be reduced to the problem described above.
Let G be a graph with Vertices set V. Let us build set S as numbers enumerating the vertices of V, and build property(x,y) as “x and y are not connected by an edge”.
This build has the complexity of n^2 * complexity of property (if not polynomial than the problem is not polynomial by its nature. otherwise, the build is polynomial).
Now, let S’ be the solution set found by the algorithm of the problem. since the set S and property are built exactly on V and the no-edge properties, S’ can easily be transformed into the solution to the IS problem.
Therefore, our problem solves a NP-complete problem after a polynomial reduction and thus is NP-complete itself. to this day, it is not known about polynomial (non brute-force) solutions for NP-complete problems.
5