Acyclicity conjecture for the optimal-predictor graph

At least 10 years old · documented by

For ρ\rho and nn, let 4Gρ,n44\mathcal{G}_{\rho,n}4 be the directed graph whose vertices are all Boolean functions of nn variables, with a directed edge from each function ff to its optimal predictor sgn⁡Tρf\operatorname{sgn} T_{\rho}f whenever they differ; if TρfT_{\rho}f is identically zero, set sgn⁡Tρf=f\operatorname{sgn} T_{\rho}f=f. A cycle-free directed graph contains no directed cycles.

Optimal-predictor acyclicity conjecture. The graph Gρ,n\mathcal{G}_{\rho,n} contains no cycles.

If true, this would make the number of ρ\rho-self-predicting functions equal to the number of connected components of Gρ,n\mathcal{G}_{\rho,n}, as described in the source; the supplied text does not state a resolution.

References

Primary source

Nir Weinberger and Ofer Shayevitz, “Self-Predicting Boolean Functions”, arXiv:1801.04103 (2019).

Additional references

2 papers in this index state this conjecture (2015–2018). The statement above is taken from the most recent of them; the others are arXiv:1508.01281.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.