Informatyka satisfiability

2

Wyjaśnianie SAT nauczycielom przedmiotów ścisłych w szkole średniej

Jestem absolwentem liceum, który interesuje się informatyką. Opracowałem fajny algorytm dla #SAT i wdrażam na nim projekt Science Fair. Mój doradca, który jest najlepszym nauczycielem przedmiotów ścisłych w mojej szkole i nauczycielem AP Comp Sci, powiedział mi, że absolutnie nie ma pojęcia, o czym jest mój projekt, i że muszę …

9 algorithms satisfiability

1

Jeśli ktoś pokazuje, że UNIKALNY k-SAT jest w P, to czy oznacza to, że P = NP?

Valiant i Vazirani udowodnili, że SAT można zredukować do UNIKALNEGO SAT przy randomizowanych probabilistycznych redukcjach czasu wielomianowego. Calabro i in . pokazał, że UNIKALNY k-SAT jest tak trudny jak k-SAT. Teraz pytanie brzmi: jeśli ktoś pokaże, że UNIKALNY k-SAT jest w P, czy oznacza to, że P = NP? Bibliografia …

9 complexity-theory satisfiability p-vs-np

1

Jaka jest nazwa problemu? (podział wykresu na trzy okładki)

Zastanawiałem się, czy ten problem ma nazwę: Biorąc pod uwagę prosty wykres, którego krawędzie są w kolorze czerwonym, niebieskim i zielonym, G = ( V, B ∪ R ∪ G )G=(V,B∪R∪G)G=(V,B\cup R\cup G), czy jest kolorowanie wierzchołków c : V→ { B , R , G }c:V→{B,R,G}c:V\to \{B,R,G\} tak, że …

9 algorithms complexity-theory graphs satisfiability colorings

2

Odnaleźć

Niech będzie językiem wszystkich formuł -CNF , tak aby przynajmniej z klauzul mogły być spełnione.LϵLϵL_\epsilon222φφ\varphi(12+ϵ)(12+ϵ)(\frac{1}{2}+\epsilon)φφ\varphi Muszę udowodnić, że istnieje st is twardy dla każdego .ϵ′ϵ′\epsilon'LϵLϵL_\epsilonNPNP\mathsf{NP}ϵ<ϵ′ϵ<ϵ′\epsilon<\epsilon' Wiemy, że może być przybliżony do presetów klauzul z redukcji . Jak mam to rozwiązać?Max2SatMax2Sat\text{Max}2\text{Sat}55565556\frac{55}{56}Max3SatMax3Sat\text{Max}3\text{Sat}

9 complexity-theory satisfiability approximation

Pytania otagowane jako satisfiability