Test Selection for AI Agents under Shrinking Permissions: Strategy Synthesis and Complexity

An artificial intelligence (AI) agent gathers information through tests before choosing an action. I study adaptive test selection when permissions to call deterministic tests and retain earlier answers can shrink during execution. Using only its current permission state, surviving labeled answers, and query count, the agent must choose an action valid in a fixed hidden world within a query budget across all permitted permission changes. Although surviving answers remain truthful, surviving test names can preserve distinctions from deleted answers, so merging tests with identical outcomes and permissions can destroy every winning strategy. Strategy synthesis from the current record is complete for nondeterministic polynomial time (NP) already with four worlds, two terminal actions, and two queries when one binary answer entry is erased across merging permission branches, whereas polynomial-time algorithms handle at most three worlds at two queries, one query for any world count, and at most two worlds at any horizon. I characterize when, across all legal strategies within the horizon, the worlds reaching every reached record are exactly those compatible with its surviving answers. This exact-replay condition is recognizable in polynomial time, makes synthesis fixed-parameter tractable in the number of worlds, and guarantees safe merging of identical tests. For a checkpoint summary stored before further adaptive queries, contexts can share a summary value precisely when one continuation strategy solves them all: when each context is individually solvable, hypergraph coloring on compatible-continuation simplicial complexes yields exact tradeoffs between summary values and remaining queries. This is the author’s manuscript of 1 November 2026.