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}