Abstract: The study of computational complexity in various algebraic structures was initiated by S. Smale, L. Blum and M. Shub in 1989, when they introduced analogues of the basic concepts of the classical theory of computability and computational complexity for fields of real and complex numbers. In particular, they defined analogues of the classes P and NP and posed problems on the coincidence of these classes for fields R and C. These problems are still open. However, later it was possible to prove the inequality P=/=NP for other algebraic systems: the additive group of real numbers (K. Meer, 1994), infinite Boolean algebras (M. Prunescu, 2002), rings of real matrices (A. Rybalov, 2004). The method developed for obtaining these results makes significant use of the properties of algebraic sets, closely related to such concepts of universal algebraic geometry as equational domains and co-domains. The talk will present new results on the inequality of classes P and NP in some rings, generalizing previous results.

Cite: Rybalov A.
P vs NP problem and universal algebraic geometry
Algebraic Geometry and Model Theory of Groups III 03-13 Sep 2025