CiteExport$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_upper_j_idt147",{id:"formSmash:upper:j_idt147",widgetVar:"widget_formSmash_upper_j_idt147",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:upper:exportLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_upper_j_idt148_j_idt150",{id:"formSmash:upper:j_idt148:j_idt150",widgetVar:"widget_formSmash_upper_j_idt148_j_idt150",target:"formSmash:upper:j_idt148:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});

(2 + ϵ)-SAT is NP-hardPrimeFaces.cw("AccordionPanel","widget_formSmash_some",{id:"formSmash:some",widgetVar:"widget_formSmash_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_all",{id:"formSmash:all",widgetVar:"widget_formSmash_all",multiple:true});
function selectAll()
{
var panelSome = $(PrimeFaces.escapeClientId("formSmash:some"));
var panelAll = $(PrimeFaces.escapeClientId("formSmash:all"));
panelAll.toggle();
toggleList(panelSome.get(0).childNodes, panelAll);
toggleList(panelAll.get(0).childNodes, panelAll);
}
/*Toggling the list of authorPanel nodes according to the toggling of the closeable second panel */
function toggleList(childList, panel)
{
var panelWasOpen = (panel.get(0).style.display == 'none');
// console.log('panel was open ' + panelWasOpen);
for (var c = 0; c < childList.length; c++) {
if (childList[c].classList.contains('authorPanel')) {
clickNode(panelWasOpen, childList[c]);
}
}
}
/*nodes have styleClass ui-corner-top if they are expanded and ui-corner-all if they are collapsed */
function clickNode(collapse, child)
{
if (collapse && child.classList.contains('ui-corner-top')) {
// console.log('collapse');
child.click();
}
if (!collapse && child.classList.contains('ui-corner-all')) {
// console.log('expand');
child.click();
}
}
2017 (English)In: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, Vol. 46, no 5, p. 1554-1573Article in journal (Refereed) Published
##### Abstract [en]

##### Place, publisher, year, edition, pages

Society for Industrial and Applied Mathematics Publications , 2017. Vol. 46, no 5, p. 1554-1573
##### Keywords [en]

Complexity dichotomy, Constraint satisfaction, Discrepancy, Hypergraph coloring, Polymorphisms, Probabilistically checkable proofs
##### National Category

Computer and Information Sciences
##### Identifiers

URN: urn:nbn:se:kth:diva-217605DOI: 10.1137/15M1006507ISI: 000416763900003Scopus ID: 2-s2.0-85032973667OAI: oai:DiVA.org:kth-217605DiVA, id: diva2:1157509
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt443",{id:"formSmash:j_idt443",widgetVar:"widget_formSmash_j_idt443",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt449",{id:"formSmash:j_idt449",widgetVar:"widget_formSmash_j_idt449",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt455",{id:"formSmash:j_idt455",widgetVar:"widget_formSmash_j_idt455",multiple:true});
##### Note

We prove the following hardness result for a natural promise variant of the classical CNF-satisfiability problem: Given a CNF-formula where each clause has width w and the guarantee that there exists an assignment satisfying at least g = [w/2]-1 literals in each clause, it is NP-hard to find a satisfying assignment to the formula (that sets at least one literal to true in each clause). On the other hand, when g = [w/2], it is easy to find a satisfying assignment via simple generalizations of the algorithms for 2-Sat. Viewing 2-Sat 2 P as tractability of Sat when 1 in 2 literals are true in every clause, and NP-hardness of 3-Sat as intractability of Sat when 1 in 3 literals are true, our result shows, for any fixed ϵ > 0, the difficulty of finding a satisfying assignment to instances of "(2 + ϵ)-Sat" where the density of satisfied literals in each clause is guaranteed to exceed 1/2+ϵ. We also strengthen the results to prove that, given a (2k +1)-uniform hypergraph that can be 2-colored such that each edge has perfect balance (at most k +1 vertices of either color), it is NP-hard to find a 2-coloring that avoids a monochromatic edge. In other words, a set system with discrepancy 1 is hard to distinguish from a set system with worst possible discrepancy. Finally, we prove a general result showing the intractability of promise constraint satisfaction problems based on the paucity of certain "weak polymorphisms." The core of the above hardness results is the claim that the only weak polymorphisms in these particular cases are juntas depending on few variables.

QC 20171116

Available from: 2017-11-16 Created: 2017-11-16 Last updated: 2018-01-13Bibliographically approved
doi
urn-nbn$(function(){PrimeFaces.cw("Tooltip","widget_formSmash_j_idt1168",{id:"formSmash:j_idt1168",widgetVar:"widget_formSmash_j_idt1168",showEffect:"fade",hideEffect:"fade",showDelay:500,hideDelay:300,target:"formSmash:altmetricDiv"});});

CiteExport$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_lower_j_idt1221",{id:"formSmash:lower:j_idt1221",widgetVar:"widget_formSmash_lower_j_idt1221",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:lower:exportLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_lower_j_idt1222_j_idt1224",{id:"formSmash:lower:j_idt1222:j_idt1224",widgetVar:"widget_formSmash_lower_j_idt1222_j_idt1224",target:"formSmash:lower:j_idt1222:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});