notesum.ai

Published at October 18

cs.CV

cs.AI

Released Date: October 18, 2024

Authors: Giuseppe De Giacomo¹, Emiliano Lorini², Timothy Parker², Gianmarco Parretti³

Aff.: ¹University of Oxford, UK; ²IRIT, CNRS, University of Toulouse, France; ³University of Rome "La Sapienza", Italy

	Complexity $(\omega,\mathcal{E},\sigma_{ag})$	Algorithm $(\omega,\mathcal{E},\sigma_{ag})$
PRAnt	pspace-C $(\omega)$ 2exptime-C $(\mathcal{E})$ poly $(\sigma_{ag})$	$\neg\textsc{CheckDom}(\neg\omega,\mathcal{E},\sigma_{ag})$
IPRAnt	2exptime-C [ $\omega$ ][ $\mathcal{E}$ ] poly $(\sigma_{ag})$	$\neg\textsc{CheckBE}(\neg\omega,\mathcal{E},\sigma_{ag})$
PRattr $(h)$	pspace-C $(\omega)$ 2exptime-C $(\mathcal{E})$ poly $[\sigma_{ag}][h]$	$\neg\textsc{CheckDom}(\neg\omega,\mathcal{E}\land\mathcal{E}_{h},\sigma_{ag})$
IPRattr $(h)$	2exptime-C $[\omega][\mathcal{E}]$ poly $[\sigma_{ag}][h]$	$\neg\textsc{CheckBE}(\neg\omega,\mathcal{E}\land\mathcal{E}_{h},\sigma_{ag})$
ARA	pspace-C $(\omega)$ 2exptime-C $(\mathcal{E})$ poly $(\sigma_{ag})$	$\textsc{CheckWin}(\omega,\mathcal{E},\sigma_{ag})\land{}$ $\textsc{ExistsWeak}(\neg\omega,\mathcal{E})$