MAX3SAT is exponentially hard to approximate if NP has positive dimension.

DOI10.1016/S0304-3975(01)00340-1zbMath1061.68065MaRDI QIDQ1853564

John M. Hitchcock

Publication date: 21 January 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

Resource-bounded measureInapproximabilityMAX3SATResource-bounded dimension

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (5)

Scaled dimension and nonuniform complexity ⋮ The size of SPP ⋮ Dimension is compression ⋮ Partial bi-immunity, scaled dimension, and NP-completeness ⋮ Pushdown dimension

Cites Work

• Almost everywhere high nonuniform complexity
• Measure, Stochasticity, and the Density of Hard Languages
• MAX SAT approximation beyond the limits of polynomial-time approximation
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: MAX3SAT is exponentially hard to approximate if NP has positive dimension.