En el problema de extensibilidad, se nos da parte de la solución y queremos decidir si podemos extenderla a una solución completa. Algunos problemas de extensibilidad se pueden resolver de manera eficiente, mientras que otros problemas de extensibilidad transforman un problema fácil en uno difícil.
Por ejemplo, el teorema de Konig-Hall establece que todos los gráficos bipartitos cúbicos son coloreables en 3 bordes, pero la versión extensible se convierte en -completa si se nos dan los colores de algunos bordes.
Estoy buscando una encuesta de problemas de extensibilidad difícil donde el problema base es fácil (o trivial como en el ejemplo anterior).
cc.complexity-theory
reference-request
graph-theory
np-hardness
Mohammad Al-Turkistany
fuente
fuente
Respuestas:
n-colorear el gráfico nxn Sudoku es trivial, pero si se le dan algunos de los colores (la versión extensible) se convierte en NP-completo.
Por "gráfico de Sudoku" me refiero al gráfico natural cuyo problema de coloración asociado es Sudoku. A saber, supongamos que es un cuadrado. La gráfica tendrá n 2 vértices, que denotaremos por ( r 1 , r 2 ; c 1 , c 2 ) para r 1 , r 2 , c 1 , cn=k2 n2 (r1,r2;c1,c2) . Para cada fijo(r1,r2), los vértices(r1,r2;∗,∗)forman unan-clique; para cada fijo(c1,c2)los vértices(∗,∗;c1,c2)forman unan-clique; y para cada fijo(r1,c1r1,r2,c1,c2∈[k]=[n−−√] (r1,r2) (r1,r2;∗,∗) n (c1,c2) (∗,∗;c1,c2) n , los vértices ( r 1 , ∗ ;(r1,c1) (r1,∗;c1,∗) n
fuente