Complexity of logical theories involving coprimality (Q1202924): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 07:10, 31 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Complexity of logical theories involving coprimality |
scientific article |
Statements
Complexity of logical theories involving coprimality (English)
0 references
22 April 1993
0 references
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)\).
0 references
computational complexity
0 references
logical theories
0 references
coprimality
0 references