The ghosts of forgotten things: A study on size after forgetting
This addresses a computational complexity issue in logic and AI, particularly for knowledge representation and reasoning, but it is incremental as it builds on existing hardness results for forgetting.
The paper tackles the problem of forgetting variables in logical formulas, showing that it can increase formula size, and proves that deciding if forgetting can be expressed within a given size is computationally hard, specifically D^p-hard in Σ^p_2 for Horn formulas and D^p_2-hard in Σ^p_3 for unrestricted formulas.
Forgetting is removing variables from a logical formula while preserving the constraints on the other variables. In spite of being a form of reduction, it does not always decrease the size of the formula and may sometimes increase it. This article discusses the implications of such an increase and analyzes the computational properties of the phenomenon. Given a propositional Horn formula, a set of variables and a maximum allowed size, deciding whether forgetting the variables from the formula can be expressed in that size is $D^p$-hard in $Σ^p_2$. The same problem for unrestricted propositional formulae is $D^p_2$-hard in $Σ^p_3$.