Gap-ETH
Statement
A -SAT formula is called satisfiable if all its clauses can be satisfied, and it has at most a fraction of satisfiable clauses if no assignment satisfies more than that fraction. Here denotes the number of clauses.
Gap-ETH. There exist constants such that no algorithm running in time can distinguish between a satisfiable -SAT formula and a -SAT formula with at most a fraction of satisfiable clauses.
Gap-ETH is a stronger quantitative variant of the Exponential Time Hypothesis used to establish algorithmic lower bounds. Under ordinary ETH, Dinur's quasilinear-length PCP gives a weaker lower bound; a linear-length PCP would imply Gap-ETH from ETH.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.