On simple expectations and observations of intelligent agents: A complexity study
This work provides foundational insights into the complexity of epistemic reasoning for agents, but it is incremental as it builds on existing logical frameworks.
The paper investigates the computational complexity of satisfaction problems for various fragments of Public Observation Logic (POL), which models agent expectations and observations in real-world scenarios, and establishes connections with Public Announcement Logic.
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.