No Efficient Disjunction or Conjunction of Switch-Lists
arXiv:2203.04788v12 citationsh-index: 17
Originality Incremental advance
AI Analysis
This addresses a theoretical limitation in computational complexity for researchers working with switch-list representations.
The paper demonstrates that disjunction of two switch-lists can cause an exponential increase in representation size, and since switch-lists can be negated without size growth, this implies conjunction also leads to exponential blow-up in general.
It is shown that disjunction of two switch-lists can blow up the representation size exponentially. Since switch-lists can be negated without any increase in size, this shows that conjunction of switch-lists also leads to an exponential blow-up in general.