3 ms·
DLC is in NP and co-NP. Very unlikely to be NP-hard. It is usually listed as one of the candidates for problems that are NP-intermediate, ie, problems in-betwee
by JohnKemeny 2y ago
DLC is in NP and co-NP. Very unlikely to be NP-hard. It is usually listed as one of the candidates for problems that are NP-intermediate, ie, problems in-between P and NP-hard (should they be different).
See e.g. https://cs.stackexchange.com/a/2765 https://cs.stackexchange.com/a/2765