Complexity of logical theories involving coprimality (Q1202924)

The author studies upper bounds on the computational complexity of some logical theories. The theory \(\text{Th}({\mathcal P}_ f(\mathbb{N}),\subseteq)\) of finite subsets of \(\mathbb{N}\) is proved to be in \(\bigcup_{c>0}\text{ATIME}\)-\(\text{ALT}(2^{cn},n)\). The same result is proved for the theories \(\text{Th}(\mathbb{N},\perp)\), \(\text{Th}(\mathbb{N},\perp,\times)\) and \(\text{Th}(\mathbb{N},\perp,\times,2x,x^ 2,2^ x)\), where \(\perp\) denotes coprimality of numbers. The theory \(\text{Th}(\mathbb{N},=,\perp)\) is proved to be in \(\bigcup_{c>0}\text{ATIME}\)-\(\text{ALT}(2^{{cn}^ 2},n)\). These upper bounds almost match the following lower bound: there is a \(c>0\) such that none of the theories \(\text{Th}(\mathbb{N},\perp)\), \(\text{Th}(\mathbb{N},\perp,\times)\) and \(\text{Th}(\mathbb{N},=,\perp)\) are in \(\text{ATIME}\)-\(\text{ALT}(2^{cn/\log n},cn)\).