5. Polynomická redukce¶

5.1. Důkaz snadnosti problému¶

Při programování používáme redukci ve směru “zprava doleva”: pokud umíme efektivně řešit problém \(B\), pak umíme efektivně řešit i problém \(A\). Pro libovolný vstup \(x\) napřed zavoláme redukční funkci \(r\) a pak spočítáme, zda \(r(x)\) patří, nebo nepatří do \(B\). Protože oba dva kroky mají polynomickou časovou složitost, má i rozhodování problému \(A\) polynomickou časovou složitost.

Jednoduchý příklad: máme funkci, která v polynomickém čase rozhoduje, zda předaný seznam obsahuje liché číslo. Chceme napsat funkci, která rozhoduje, zda předaný seznam obsahuje liché číslo na některé liché pozici (při počítání pozic od 1). Rozmyslete si, jak by mohla vypadat redukční funkce. Možné řešení:

#### Problem B ####
# Vraci True, pokud seznam cisel 'numbers' obsahuje liche cislo
def contains_odd_number(numbers):
    for number in numbers:
        if number % 2 == 1:
            return True
    return False

#### Redukce z A na B ####
# Redukuje problem licheho cisla na liche pozici na problem licheho cisla kdekoliv
def reduction(numbers):
    # Vrat novy seznam vytvoreny z puvodniho vzitim kazdeho druheho prvku
    return numbers[::2]

#### Problem A ####
# Vraci True, pokud seznam obsahuje liche cislo na liche pozici
def has_odd_number_at_odd_position(numbers):
    return contains_odd_number(reduction(numbers))

#### Test ####
print(has_odd_number_at_odd_position([4, 7, 6, 2]))  # False
print(has_odd_number_at_odd_position([4, 2, 7, 6]))  # True

Složitějším příkladem by mohla být třeba redukce problému maximálního párování v bipartitním grafu na problém maximálního toku.

Redukce “zprava doleva” můžou být užitečné i v případě, kdy je problém \(B\) těžký, ale existují pro něj velmi dobré osvědčené solvery (např. SAT nebo úloha lineárního programování).

5.2. Důkaz těžkosti problému¶

Směr “zleva doprava” pak můžeme využít k tomu, abychom ukázali, že nějaký problém nelze řešit efektivně – pokud o problému \(A\) víme, že není jednoduchý (je NP-těžký), pak ani problém \(B\) nemůže být jednoduchý (tj. je taky NP-těžký).

Příklad: Víme, že problém rozhodování existence k-kliky (úplný podgraf velikosti k) v grafu je NP-těžký. (A pokud to ještě nevíte, tak si vyřešte úlohu 83 ve sbírce a budete to vědět.) S využitím této znalosti se pokusíme ukázat, že problém rozhodovaní existence nezávislé množiny velikosti k v zadaném grafu je NP-těžký (nezávislá množina = podmnožina vrcholů taková, že žádné dva vybrané vrcholy spolu nesousedí).

Zkuste vymyslet redukci z problému kliky na problém nezávislé množiny.

Řešení spočívá v následujícím pozorování: k-klika existuje v grafu právě tehdy, když v doplňku tohoto grafu existuje nezávislá množina velikosti k (doplňek grafu = graf na stejné množině vrcholu, v němž jsou hrany právě mezi těmi vrcholy, mezi kterými v původním grafu hrana není). Redukční funkce tak musí pro dvojici \((G, k)\) vrátit \((G^c, k)\), kde \(G^c\) je doplněk grafu \(G\). Ukážeme, že lze tuto redukční funkci implementovat s polynomickou časovou složitostí. Vytvořit rychle doplněk grafu je jednoduché (a rychlé):

# Priklad grafu v reprezentaci seznamu sousedu
example_graph = {
      'A': ['B', 'D'],
      'B': ['A', 'C'],
      'C': ['B'],
      'D': ['A', 'E'],
      'E': ['D'],
}

# Vraci doplnek zadaneho grafu
def compute_complement(graph):
    nodes = graph.keys()
    complement = {}
    for node in nodes:
        complement[node] = [n for n in nodes if n != node and n not in graph[node]]
    return complement

print(compute_complement(example_graph))

Redukční funkce s polynomickou časovou složitostí pak může vypadat takto:

def reduction(graph, k):
    return compute_complement(graph), k

Pokud bychom uměli problém nezávislé množiny řešit rychle (tj. problém by nebyl NP-těžký), pak bychom mohli i problém k-kliky řešit rychle tak, že napřed zavoláme redukční funkci a na výsledek pak zavoláme onen pro-spor-předpokládaný rychlý řešič problému nezávislé množiny. To by však byl spor s NP-těžkostí problému k-kliky. Předpoklad tedy neplatí a problém nezávislé množiny je NP-těžký, což jsme chtěli ukázat.

# Pro spor predpokladejme, ze umime resit problem B v polynomickem case
from impossibility import polynomial_independent_set

# Redukce problemu kliky na problem nezavisle mnoziny
def reduction(graph, k):
    return compute_complement(graph), k

# Vraci doplnek zadaneho grafu
def compute_complement(graph):
    nodes = graph.keys()
    complement = {}
    for node in nodes:
        complement[node] = [n for n in nodes if n != node and n not in graph[node]]
    return complement


# Rozhodne v polynomickem case, zda graf obsahuje kliku dane velikosti
def polynomial_clique(graph, k):
    # Hvezdicka slouzi k rozbaleni vracene n-tice do sekvence argumentu
    return polynomial_independent_set(*reduction(graph, k))

print(polynomial_clique(graph, 3))

Poznámka: V uvedeném případě by se samozřejmě šlo obejít bez funkce reduction a psát rovnou:

def polynomial_clique(graph, k):
    return polynomial_independent_set(compute_complement(graph), k)