# Learning Temporal Properties is NP-hard

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Dec 2023.

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

- [Learning Linear Temporal Specifications from Demonstrations with Uncertainty](https://mlsanity.com/paper/2607.10918/) (2026)

## Abstract (arXiv)

We investigate the complexity of LTL learning, which consists in deciding given a finite set of positive ultimately periodic words, a finite set of negative ultimately periodic words, and a bound B given in unary, if there is an LTL-formula of size less than or equal to B that all positive words satisfy and that all negative violate. We prove that this decision problem is NP-hard. We then use this result to show that CTL learning is also NP-hard. CTL learning is similar to LTL learning except that words are replaced by finite Kripke structures and we look for the existence of CTL formulae.