# Statistical EL is ExpTime-complete

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

## Key facts

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

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

- [Approximating Probabilistic Inference in Statistical EL with Knowledge Graph Embeddings](https://mlsanity.com/paper/2407.11821/) (2024)
- [Scalable Uncertainty Reasoning in Knowledge Graphs](https://mlsanity.com/paper/2605.16568/) (2026)

## Abstract (arXiv)

We show that the consistency problem for Statistical EL ontologies, defined by Pe~naloza and Potyka, is ExpTime-hard. Together with existing ExpTime upper bounds, we conclude ExpTime-completeness of the logic. Our proof goes via a reduction from the consistency problem for EL extended with negation of atomic concepts.