On the generic complexity of graph 3-coloring problems | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2025. № 69. DOI: 10.17223/20710410/69/8

In this paper, we study the generic complexity of two versions of the graph 3-coloring problem: the graph 3-coloring recognition problem and the graph 3-coloring search problem. For both problems, no efficient polynomial algorithms are known. The 3-coloring search problem is used in the well-known Blum zero-knowledge cryptographic protocol. We propose a polynomial generic algorithm for the graph 3-coloring recognition problem. For the 3-coloring search problem, we prove that if P = NP and P = BPP, then there is a subproblem of this problem for which there is no polynomial generic algorithm. The obtained result provides theoretical justification for applying the 3-coloring search problem in cryptography, an application where breaking a cryptographic algorithm must be difficult for almost all inputs. To prove this theorem, we use the method of generic amplification, which allows to construct generically hard problems from the problems hard in the classical sense.