8 found
Sort by:
  1. Mihai Prunescu (2008). An Undecidable Property of Recurrent Double Sequences. 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 (6 more)  
     
    My bibliography  
     
    Export citation  
  2. Mihai Prunescu (2006). Structure with Fast Elimination of Quantifiers. 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 (4 more)  
     
    My bibliography  
     
    Export citation  
  3. Mihai Prunescu (2006). Undecidable and Decidable Restrictions of Hilbert's Tenth Problem: Images of Polynomials Vs. Images of Exponential Functions. Mathematical Logic Quarterly 52 (1):14-19.
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  4. Mihai Prunescu (2003). Diophantine Properties of Finite Commutative Rings. 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.
    No categories
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  5. Mihai Prunescu (2003). P ≠ NP for All Infinite Boolean Algebras. Mathematical Logic Quarterly 49 (2):210-213.
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  6. Mihai Prunescu (2002). A Model-Theoretic Proof for {$\Roman P\Neq {\Rm NP}$} Over All Infinite Abelian Groups. Journal of Symbolic Logic 67 (1):235-238.
    Translate to English
    | Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  7. Mihai Prunescu (2002). An Isomorphism Between Monoids of External Embeddings About Definability in Arithmetic. Journal of Symbolic Logic 67 (2):598-620.
    We use a new version of the Definability Theorem of Beth in order to unify classical theorems of Yuri Matiyasevich and Jan Denef in one structural statement. We give similar forms for other important definability results from Arithmetic and Number Theory.
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  8. Mihai Prunescu (2002). A Model-Theoretic Proof for P ≠ NP Over All Infinite Abelian Groups. 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 (4 more)  
     
    My bibliography  
     
    Export citation