Premium
On P Versus NP for Parameter‐Free Programs Over Algebraic Structures
Author(s) -
Hemmerling Armin
Publication year - 2001
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/1521-3870(200101)47:1<67::aid-malq67>3.0.co;2-v
Subject(s) - quantifier elimination , computation , mathematics , equivalence (formal languages) , invariant (physics) , algebraic number , discrete mathematics , algebra over a field , pure mathematics , algorithm , mathematical analysis , mathematical physics
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.