Hlavní navigace

Názor ke článku Obtížnost hledání min od Ivorne - Hledání min podle mě není NP-hard. Jak by...

  • 27. 3. 2014 0:54

    Ivorne (neregistrovaný) 147.32.123.---

    Hledání min podle mě není NP-hard. Jak by jste převedl SAT na hledání min?

    Počet kroků hry je polynomiální k velikosti herního pole. Předpokládáme-li, že v každém tahu půjde vyplnit alespoň jedno políčko, tak průchod všemi políčky je také polinomiální. A vyřešitelnost případně řešení každého políčka závisí pouze na sousedech, takže to je konstantní složitost.