# The ghosts of forgotten things: A study on size after forgetting

arXiv: https://arxiv.org/abs/2005.04123 · HTML: https://mlsanity.com/paper/2005.04123/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 May 2020.

## Built on by (most cited first, 2 of 2)

- [Superredundancy: A tool for Boolean formula minimization complexity analysis](https://mlsanity.com/paper/2205.00762/) (2022)
- [Abductive forgetting](https://mlsanity.com/paper/2209.12825/) (2022)

## Abstract (arXiv)

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 Dp-hard in Sigmap2. The same problem for unrestricted propositional formulae is Dp2-hard in Sigmap3.