论文标题
被遗忘的事物的幽灵：忘记后的大小研究
The ghosts of forgotten things: A study on size after forgetting
论文作者
论文摘要
忘记是从逻辑公式中删除变量，同时保留其他变量的约束。尽管是一种减少的形式，但它并不总是会降低公式的大小，有时可能会增加。本文讨论了这种增加的含义，并分析了现象的计算特性。给定命题号角公式，一组变量和最大允许的大小，决定是否可以以$ d^p $ -hard表示忘记公式的变量，in $ d^p $ - hard，in $σ^p_2 $。无限制的命题公式的同样问题是$ d^p_2 $ -hard，in $σ^p_3 $。
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$.
