# On simple expectations and observations of intelligent agents: A complexity study

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 25 references that are in the map.
- First posted on arXiv 5 Jun 2023.

## Builds on (most cited first, 4 of 4)

- [Beyond knowing that: a new generation of epistemic logics](https://mlsanity.com/paper/1605.01995/) (2016)
- [On the Complexity of Dynamic Epistemic Logic](https://mlsanity.com/paper/1310.6406/) (2013)
- [Quantifying over Boolean announcements](https://mlsanity.com/paper/1712.05310/) (2017)
- [On verifying expectations and observations of intelligent agents](https://mlsanity.com/paper/2205.00784/) (2022)

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

- [Reasoning About Knowledge on Regular Expressions is 2EXPTIME-complete](https://mlsanity.com/paper/2508.09784/) (2025)

## Abstract (arXiv)

Public observation logic (POL) reasons about agent expectations and agent observations in various real world situations. The expectations of agents take shape based on certain protocols about the world around and they remove those possible scenarios where their expectations and observations do not match. This in turn influences the epistemic reasoning of these agents. In this work, we study the computational complexity of the satisfaction problems of various fragments of POL. In the process, we also highlight the inevitable link that these fragments have with the well-studied Public announcement logic.