Acyclicity conjecture for the optimal-predictor graph
For and , let be the directed graph whose vertices are all Boolean functions of variables, with a directed edge from each function to its optimal predictor whenever they differ; if is identically zero, set . A cycle-free directed graph contains no directed cycles.
Optimal-predictor acyclicity conjecture. The graph contains no cycles.
If true, this would make the number of -self-predicting functions equal to the number of connected components of , 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
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.