# Consequence of NP-complete, and DP-complete w.r.t. randomized reductions

If a problem is NP-complete with respect to randomized (polynomial time) reductions, but not with respect to deterministic reductions, then we have P $$\neq$$ BPP (See Question 2 here and its answer).

Suppose a decision problem is proved to be NP-complete; and it is also proved to be DP-complete with respect to randomized reductions. Does this have any real consequence?

Context (updated)
Given a graph $$G$$, it is DP-complete with respect to randomized reductions to test whether $$G$$ has exactly one 3-colouring upto swapping of colours [2]. I thought the same problem is coNP-complete because the "another solution" problem associated with 3-colouring is NP-complete [1]. My reasoning was wrong. Only the associated promise problem (give a promise that the graph has a 3-colouring) is coNP-complete (two different 3-colourings together serve as a no certificate). If that promise is not given, there is no obvious way to give a no certificate in the case when the graph is not 3-colourable.

[1] Dailey, David P., Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete, Discrete Math. 30, 289-293 (1980). ZBL0448.05030.

[2] Barbanchon, Régis, On unique graph 3-colorability and parsimonious reductions in the plane, Theor. Comput. Sci. 319, No. 1-3, 455-482 (2004). ZBL1043.05043.

• Since this has been known for 17 years, presumably all consequences would have been worked out by now. Apr 21, 2021 at 5:51
• @YuvalFilmus Sure, but were there any actual consequences? Apr 21, 2021 at 5:52
• They ought to have been mentioned by Barbanchon in their paper. Apr 21, 2021 at 5:52