×

On generic complexity of the existential theories. (Russian. English summary) Zbl 1477.03159

Summary: Many problems about finite graphs and finite fields can be formulated in the universal algebraic geometry, where these objects are considered as algebraic structures in the given language. Algebraic geometry over such objects is closely related to properties of existential theories. From a practical point of view, the most important are questions about decidability and computational complexity of these theories. In this paper we study the computational complexity of existential theories of algebraic structures of finite predicate language. It is known that the existential theory of any algebraic structure with more than one element is NP-hard. We prove that under the conditions \(\text{P} \neq \text{NP}\) and \(\text{P} = \text{BPP} \), for this theories there is no polynomial strongly generic algorithm. To prove this theorem we use the method of generic amplification, which allows to construct generically undecidable problems from the problems undecidable in the classical sense. The main ingredient of this method is a technique of cloning, which unites inputs of the problem together in the large enough sets of equivalent inputs. Equivalence is understood in the sense that the problem is solved similarly for them.

MSC:

03D15 Complexity of computation (including implicit computational complexity)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDFBibTeX XMLCite
Full Text: DOI MNR

References:

[1] Daniyarova E. Y., Myasnikov A. G., Remeslennikov V. N., Algebraic Geometry over Algebraic Structures, SB RAS Publ., Novosibirsk, 2016, 288 pp. (in Russian) · Zbl 1240.08002
[2] Kapovich I., Miasnikov A., Schupp P., Shpilrain V., “Generic-case complexity, decision problems in group theory and random walks”, J. Algebra, 264:2 (2003), 665-694 · Zbl 1041.20021 · doi:10.1016/S0021-8693(03)00167-4
[3] Garey M., Johnson D., Computers and Intractability, Freeman & Co, N. Y., 1979, 340 pp. · Zbl 0411.68039
[4] Impagliazzo R., Wigderson A., “\(P =\) BPP unless E has subexponential circuits: Derandomizing the XOR Lemma”, Proc. 29th STOC, ACM, El Paso, 1997, 220-229 · Zbl 0962.68058
[5] Knuth D. E., The Art of Computer Programming, Addison-Wesley, Reading, Massachusetts, 1997 · Zbl 0883.68015
[6] Rybalov A., “On generic complexity of the validity problem for Boolean formulas”, Prikladnaya Diskretnaya Matematika, 2016, no. 2(32), 119-126 (in Russian) · Zbl 1490.68114
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.