0
$\begingroup$

A 3-SAT family is an algorithm that given a positive integer $n$ outputs a 3-SAT problem in $n$ clauses in $O(n^{1+\epsilon})$ time ($\epsilon$ is to allow for the indexing of the variables).

A solution of a 3-SAT family is an algorithm that given a positive integer decides whether the corresponding 3-SAT problem is satisfiable.

Can you give an example of a 3-SAT family such that the time complexity of each its solution is $\omega(n^2)$? What about $\omega(n^{3})$ or $\omega(n^{1000})$?

The examples should not depend on $P\neq NP$ or other conjectures.

Improve this question
$\endgroup$
4
  • $\begingroup$ OP states $3$-SAT and $n$ clauses and so sparsification lemma (where we require $\Theta(n)$ clauses) is not applicable and so perhaps the problem makes sense. $\endgroup$
    – Turbo
    Commented Oct 18, 2021 at 14:04
  • 3
    $\begingroup$ If I understand the question correctly, then it is still wide open. The best known lower bounds that we have on any natural problem in NP are linear. $\endgroup$
    – Noah Stephens-Davidowitz
    Commented Oct 18, 2021 at 14:38
  • $\begingroup$ @NoahStephens-Davidowitz Is this mentioned in some paper? $\endgroup$
    – user409739
    Commented Oct 18, 2021 at 15:03
  • 1
    $\begingroup$ Here's the current state of the art: eccc.weizmann.ac.il/report/2021/023 . It's for circuits, which might not be the model that you're thinking of. $\endgroup$
    – Noah Stephens-Davidowitz
    Commented Oct 18, 2021 at 16:52

0

Reset to default

You must log in to answer this question.