Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2604.16327 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- In \cite{Standish25c}, I explored the connection between star complexity and information based complexity. Because of the numerical difficulty in computing star complexity, I introduced a proxy measure that is an upper bound to star complexity, and showed a strong albeit non-linear relationship between the measures. In this paper, I introduce a tighter upper bound, by exploiting the well-known ABC package used to optimise logic circuits. In testing the new measure, I found that I had been computing the {\em formula complexity} variant of star complexity, rather than the tighter {\em circuit complexity} variant. Since Jukna clearly states the connection between star complexity and circuit complexity, I have modified the graph walking algorithm to capture circuit complexity rather than formula complexity. With this new ABC-based measure, applied to a set of 1000 500 vertex Erdös-Renyi graphs, a more linear relationship between star complexity and information based complexity is found.