The non-approximability of non-Boolean predicates

DOI10.1007/3-540-44666-4_27MaRDI QIDQ4780798zbMATH OpenFDO

Authors Lars Engebretsen

Publication date 21 November 2002

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2129/21290241

Mathematics Subject Classification ID

Logic programming (68N17) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Recommendations

• The Nonapproximability of Non-Boolean Predicates
• Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness
• Approximation algorithm for non-Boolean \textsc{Max}-\(k\)-CSP
• Approximation algorithm for non-Boolean MAX k-CSP
• Near-optimal NP-hardness of approximating \textsc{Max} \(k\)-\(\mathrm{CSP}_R\)

Cited in

(11)

• The approximability of non-Boolean satisfiability problems and restricted integer programming
• Inapproximability results for equations over finite groups
• Parity is positively useless
• Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness
• A characterization of hard-to-cover CSPs
• 3-bit dictator testing: 1 vs. 5/8
• The Nonapproximability of Non-Boolean Predicates
• P ≠ NP for all infinite Boolean algebras
• scientific article; zbMATH DE number 922577 (Why is no real title available?)
• The Complexity of Somewhat Approximation Resistant Predicates
• Inapproximability results for equations over infinite groups

This page was built for publication: The non-approximability of non-Boolean predicates

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4780798)