Closed austin-marcus closed 8 months ago
@jcrozum I believe your new implementation resolves this issue, or at least makes these comments irrelevant.
It might be good to mention the horrendous time complexity of the problem somewhere.
Closing this because we have a completely new two symbol symmetry implementation.
For some functions, the symmetry computation will hang. I have killed it after 20 minutes. In some cases it consumed more than 16 GB of RAM.
This occurrence is strongly correlated with the number of prime implicants the function has. This makes sense because the more prime implicants, the more subsets the algorithm may need to explore. This grows combinatorically with the number of prime implicants.
I found that skipping over the section in
two_symbol_symmetry
that attempts to simplify the TS schemata is the slowest part, as in some cases it has to expand a TS schema into its prohibitively large number of literal schemata.The node erbb24 in the EGFR & ErbB Signaling network of the cell collective is an example function that has this issue. The simplification part would need to expand to $12!\times 2^{11}$ literal schemata. Skipping this makes it complete in a couple seconds.
However, this appears to not be the only cause of slow runtime.