7 found
Order:
  1. A Model-Theoretic Proof for P ≠ NP Over All Infinite Abelian Groups.Mihai Prunescu - 2002 - Journal of Symbolic Logic 67 (1):235 - 238.
    We give a model-theoretic proof of the fact that for all infinite Abelian groups P ≠ NP in the sense of binary nondeterminism. This result has been announced 1994 by Christine Gabner.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark  
  2.  59
    Diophantine Properties of Finite Commutative Rings.Mihai Prunescu - 2003 - Archive for Mathematical Logic 42 (3):293-302.
    Simple observations on diophantine definability over finite commutative rings lead to a characterization of those rings in terms of their diophantine behavior.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark  
  3.  14
    Non-Effective Quantifier Elimination.Mihai Prunescu - 2001 - Mathematical Logic Quarterly 47 (4):557-562.
    Genera connections between quantifier elimination and decidability for first order theories are studied and exemplified.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  4.  23
    An Undecidable Property of Recurrent Double Sequences.Mihai Prunescu - 2008 - Notre Dame Journal of Formal Logic 49 (2):143-151.
    For an arbitrary finite algebra $\g A = (A, f, 0, 1)$ one defines a double sequence $a(i,j)$ by $a(i,0)\!=\!a(0,j)\! =\! 1$ and $a(i,j) \!= \!f( a(i, j-1) , a(i-1,j) )$.The problem if such recurrent double sequences are ultimately zero is undecidable, even if we restrict it to the class of commutative finite algebras.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark  
  5.  20
    P ≠ NP for All Infinite Boolean Algebras.Mihai Prunescu - 2003 - Mathematical Logic Quarterly 49 (2):210-213.
    We prove that all infinite Boolean rings have the property P ≠ NP according to the digital nondeterminism.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  6.  17
    Structure with Fast Elimination of Quantifiers.Mihai Prunescu - 2006 - Journal of Symbolic Logic 71 (1):321 - 328.
    A structure of finite signature is constructed so that: for all existential formulas $\exists ??\varphi (??,??)$ and for all tuples of elements $??$ of the same length as the tuple $??$, one can decide in a quadratic time depending only on the length of the formula, if $\exists ??\varphi (??,??)$ holds in the structure. In other words, the structure satisfies the relativized model-theoretic version of P=NP in the sense of [4]. This is a model-theoretical approach to results of Hemmerling and (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark  
  7.  13
    Undecidable and Decidable Restrictions of Hilbert's Tenth Problem: Images of Polynomials Vs. Images of Exponential Functions.Mihai Prunescu - 2006 - Mathematical Logic Quarterly 52 (1):14-19.
    Classical results of additive number theory lead to the undecidability of the existence of solutions for diophantine equations in given special sets of integers. Those sets which are images of polynomials are covered by a more general result in the second section. In contrast, restricting diophantine equations to images of exponential functions with natural bases leads to decidable problems, as proved in the third section.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark