1
$\begingroup$

I went through Def 2.1 of this paper, where the approximation version of max-LINSAT is defined as follows.


Let $\mathbb{F}_p$ be a finite field.

Input: For each $i=1,\cdots,m$, let $F_i\subset \mathbb{F}_p$ be an arbitary subset of $\mathbb{F}_p$, which yields a corresponding constraints $$\sum_{j=1}^{n} B_{ij}x_j \in F_i.$$

Goal: The max-LINSAT problem is to find $\textbf{x}\in \mathbb{F}_p^n$ satisfying as many as possible of these $m$ constraints.


Let us define $\alpha = l/m$ as an approximation ratio, where $l$ is the number of satisfied constraints.

Question 1: What is the threshold value of $\alpha$ after which it becomes $\mathsf{NP}$-hard to approximate?


My attempt: I am going through this classical paper by Hastad, where the implication of $\mathsf{PCP}$ on the hardness of approximation for several variants of $\mathsf{SAT}$ is derived. Second row of Table-1 implies $\alpha=1/p+\epsilon$ for $\epsilon>0$ for problem E3-LIN-p.

Here, E3-LIN-p: given a system $m$ of linear equations over $\mathbb{F}_p$ , with exactly $k$ variables in each equation, to find x that maximizes the number of satisfied equations.

I find max-LINSAT very close to E3-Lin-p, as both are about m linear equations over $\mathbb{F}_p$. The only difference is the bound on the number of variables in each equation. One can reduce an instance of max-LINSAT to E3-Lin-p similar to how we reduce $k$-$\mathsf{SAT}$ to 3ドル$-$\mathsf{SAT}$ by introducing new clauses. This is a time- and space-efficient process.

My conclusion: Since the result mentioned in the second row of Table 1 in Hastad's paper is independent of the number of clauses. Thus, the threshold of $\alpha=1/p+\epsilon$ for any $\epsilon>0$ is equally valid for both max-LINSAT and E3-Lin-p.


Question 2: Is the above argument valid?

asked Nov 10 at 15:46
$\endgroup$

0

Know someone who can answer? Share a link to this question via email, Twitter, or Facebook.

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.