Change search
ReferencesLink to record
Permanent link

Direct link
On the np-hardness of max-not-2
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.ORCID iD: 0000-0002-5379-345X
2014 (English)In: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, Vol. 43, no 1, 179-193 p.Article in journal (Refereed) Published
Abstract [en]

We prove that, for any epsilon > 0, given a satisfiable instance of Max-NTW (Not-2), it is NP-hard to find an assignment that satisfies a fraction 5/8 + epsilon of the constraints. This, up to the existence of epsilon, matches the approximation ratio obtained by the trivial algorithm that just picks an assignment at random, and thus the result is tight. Said equivalently, the result proves that Max-NTW is approximation resistant on satisfiable instances, and this makes complete our understanding of arity three maximum constraint satisfaction problems with regards to approximation resistance.

Place, publisher, year, edition, pages
2014. Vol. 43, no 1, 179-193 p.
Keyword [en]
constraint satisfaction, approximation resistance, probabilistically checkable proofs
National Category
Computer Science Mathematics
URN: urn:nbn:se:kth:diva-144972DOI: 10.1137/120882718ISI: 000333538300009ScopusID: 2-s2.0-84896917344OAI: diva2:716096
EU, European Research Council, 226203

QC 20140508

Available from: 2014-05-08 Created: 2014-05-05 Last updated: 2014-05-08Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Håstad, Johan
By organisation
Theoretical Computer Science, TCS
In the same journal
SIAM journal on computing (Print)
Computer ScienceMathematics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 96 hits
ReferencesLink to record
Permanent link

Direct link