Back to Search
Start Over
On P Versus NP for Parameter-Free Programs Over Algebraic Structures.
- Source :
-
Mathematical Logic Quarterly . Jan2001, Vol. 47 Issue 1, p67-92. 26p. - Publication Year :
- 2001
-
Abstract
- Based on the computation mode introduced in [13], we deal with the time complexity of computations over arbitrary first-order structures.The main emphasis is on parameter-free computations. Some transfer results for solutions of P versus NP problems as well as relationships to quantifier elimination are discussed. By computation tree analysis using first-order formulas, it follows that P versus NP solutions and other results of structural complexity theory are invariant under elementary equivalence of structures. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 09425616
- Volume :
- 47
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- Mathematical Logic Quarterly
- Publication Type :
- Academic Journal
- Accession number :
- 13585393
- Full Text :
- https://doi.org/10.1002/1521-3870(200101)47:1<67::AID-MALQ67>3.0.CO;2-V