Set Membership Time

As I said in the last post, GEP can be used to solve set membership problems. By set membership I mean problems that can naturally be represented as having some set, and trying to find a subset of this set with a certain property. Subset sum, partition, SAT (I'm probably going to do 3-SAT) , and a lot of other problems fall into this category. This is interesting because SAT has such a rich history and use, both in direct practical applications and because of its importance in the study of NP and NP-complete problems. The representation that I am planning on using is so simple and obvious that I am surprised no one has done this yet (actually I'm not sure this hasn't been done, but I've not been able to find a paper related to it at all). The setup is with set operations as operator, and each terminal as a set containing one element (the id of the variable in the case of boolean satisfiability) as well as the universe set (I'm not sure I will include this yet) and the empty set. This will allow a single individual to encode an expression whose result is a set. This can be the set of boolean variables that are true out of the total set of variables. In general, this will result in one subset, and another can be constructed as U/S where S is the subset created, U is the Universe and / is 'remove'. The only real problem with this method is it does not extend easily to multi subset problems like graph coloring (each color could be a set and the vertexes would be the items in the subsets). This means that the only way to use this method to solve that type of problem is reduction, which I will be avoiding so I can focus on making this method work as well as possible.
In the next post I will discuss some of the issues involved in this method, and the ever present problem of scalability and how it can be addressed with GEP.