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.

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.