Сложные проблемы расширения

В проблеме расширяемости нам дают часть решения, и мы хотим решить, можем ли мы расширить ее до полного решения. Некоторые проблемы расширяемости эффективно разрешимы, в то время как другие проблемы расширяемости превращают легкую проблему в сложную.

Например, теорема Кенига-Холла утверждает, что все кубические двудольные графы раскрашиваются на 3 ребра, но версия расширяемости становится -полной,$NP$ если нам даны цвета некоторых ребер.

Я ищу обзорную статью о трудностях с расширяемостью, где базовая проблема проста (или тривиальна, как в примере выше).

n-раскраска графа судоку nxn тривиальна, но если вам даны некоторые цвета (версия расширяемости), он становится NP-полным.

Под «графом Судоку» я подразумеваю естественный граф, с которым связана проблема окраски Судоку. А именно, предположим$n=k^2$это квадрат. График будет иметь$n^2$ вершины, которые мы будем обозначать $(r_1, r_2; c_1, c_2)$ за $r_1,r_2,c_1,c_2 \in [k] = [\sqrt{n}]$, Для каждого фиксированного$(r_1,r_2)$вершины $(r_1, r_2; *, *)$ для мужчин $n$-клика; за каждый фиксированный$(c_1, c_2)$ вершины $(*, *; c_1, c_2)$ для мужчин $n$-клика; и для каждого фиксированного$(r_1, c_1)$вершины $(r_1, *; c_1, *)$ для мужчин $n$-клика.