Original title:
Upper bounds for (k,s)-SAT
Translated title:
Upper bounds for (k,s)-SAT
Authors:
Jurenka, David ; Szeider, Stefan (advisor) ; Dantchev, Stefan (referee) Document type: Bachelor's theses
Year:
2011
Language:
eng Abstract:
[eng][cze] While studying the (k, s)-SAT problem, one encounters a function f : N → N demarcating the boundary between trivial and NP-hard variants of this problem. However, the exact values of f (k), for k > 4, are not known. In this paper, we investigate the function f, find its upper bounds for small values of k and generate minimal instances of (k, s)-CNF formulas certifying these bounds. e upper bounds are obtained by implementing a recently published heuristic. e computation is subsequently parallel- ized in order to exploit the possibilities of high-performance computing grids. In addition, a number of related theoretical results are obtained. We disprove a recent lower bound for f, establish a lower bound on the size of (k, s)-SAT enforcers and improve on the current factor for inapproximab- ility of MAX-(3, 4)-SAT.Při studiu problému (k, s)-SAT narážíme na funkci f : N → N vyme- zující hranici mezi triviálními a NP-těžkými variantami tohoto problému. Nicméně přesné hodnoty f (k) pro k > 4 nejsou známy. Tato práce se zabývá funkcí f, hledáním jejích horních odhadů pro ma- lé hodnoty k a generováním minimálních formulí (k, s)-CNF dokládajících tyto odhady. Horní odhady jsou získány implementací heuristiky nedáv- no popsané v časopisecké literatuře. Výpočet je následně paralelizován pro využití potenciálu počítačových clusterů pro HPC. Dále je dokázáno několik teoretických výsledků. Vyvrátíme jeden ne- dávný dolní odhad pro f, zavedeme dolní odhad velikosti vynucujících for- mulí pro (k, s)-SAT a zlepšíme stávající faktor neaproximovatelnosti pro- blému MAX-(3, 4)-SAT.
Keywords:
(k,s)-SAT; critical function; hypergraph 2-colouring; inapproximability; minimum enforcers; (k,s)-SAT; 2-barvení hypergrafů; kritická funkce; minimální vynucující formule; neaproximovatelnost
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/50583