P versus np and computability theoretic constructions in complexity theory over algebraic structures
Journal of Symbolic Logic 69 (1):39-64 (2004)
| Abstract | We show that there is a structure of countably infinite signature with $P = N_{2}P$ and a structure of finite signature with $P = N_{1}P$ and $N_{1}P \neq N_{2}P$ . We give a further example of a structure of finite signature with $P \neq N_{1}P$ and $N_{1}P \neq N_{2}P$ . Together with a result from [10] this implies that for each possibility of P versus NP over structures there is an example of countably infinite signature. Then we show that for some finite ℒ the class of ℒ-structures with $P = N_{1}P$ is not closed under ultraproducts and obtain as corollaries that this class is not $\delta$ -elementary and that the class of ᵍ-structures with $P \neq N_{1}P$ is not elementary. Finally we prove that for all f dominating all polynomials there is a structure of finite signature with the following properties: $P \neq N_{1}P$ . $N_{1}P \neq N_{2}P$ , the levels $N_{2}TIME(n^{i})$ of $N_{2}P$ and the levels $N_{1}TIME(n^{i})$ of $N_{1}P$ are different for different i, indeed $DTIME(n^{i'}) \nsubseteq N_{2}TIME(n^{i})$ if $i' \textgreater i$ ; $DTIME(f) \nsubseteq N_{2}P$ , and $N_{2}P \nsubseteq DEC$ . DEC is the class of recognizable sets with recognizable complements. So this is an example where the internal structure of $N_{2}P$ is analyzed in a more detailed way. In our proofs we use methods in the style of classical computability theory to construct structures except for one use of ultraproducts | |||||||||
| Keywords | No keywords specified (fix it) | |||||||||
| Categories | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,672 |
| External links |
  Try with proxy. |
| Through your library | Configure |
Similar books and articlesLauri Hella, Phokion G. Kolaitis & Kerkko Luosto (1996). Almost Everywhere Equivalence of Logics in Finite Model Theory. Bulletin of Symbolic Logic 2 (4):422-443.
Ian Hodkinson (1994). Finite H-Dimension Does Not Imply Expressive Completeness. Journal of Philosophical Logic 23 (5):535 - 573.
H. D. MacPherson, M. Pouzet & R. E. Woodrow (1992). Countable Structures of Given Age. Journal of Symbolic Logic 57 (3):992-1010.
B. Sh Kulpeshov (1998). Weakly o-Minimal Structures and Some of Their Properties. Journal of Symbolic Logic 63 (4):1511-1528.
Paul John King, Kiril Ivanov Simov & Bjørn Aldag (1999). The Complexity of Modellability in Finite and Computable Signatures of a Constraint Logic for Head-Driven Phrase Structure Grammar. Journal of Logic, Language and Information 8 (1):83-110.
M. Andrew Moshier & Carl J. Pollard (1994). The Domain of Set-Valued Feature Structures. Linguistics and Philosophy 17 (6):607 - 631.
Ian Hodkinson & Martin Otto (2003). Finite Conformal Hypergraph Covers and Gaifman Cliques in Finite Structures. Bulletin of Symbolic Logic 9 (3):387-405.
A. C. Walczak-Typke (2005). The First-Order Structure of Weakly Dedekind-Finite Sets. Journal of Symbolic Logic 70 (4):1161 - 1170.
I. M. Hodkinson & H. D. Macpherson (1988). Relational Structures Determined by Their Finite Induced Substructures. Journal of Symbolic Logic 53 (1):222-230.
Robert Goldblatt (2001). Quasi-Modal Equivalence of Canonical Structures. Journal of Symbolic Logic 66 (2):497-508.
Analytics
Monthly downloads |
Added to index2009-02-05Total downloads8 ( #123,036 of 549,067 )Recent downloads (6 months)1 ( #63,185 of 549,067 )How can I increase my downloads? |
My notes
Discussion
