From a paper

An AND-compression is a deterministic polynomial-time algorithm that maps a set of SAT-instances $x_1,\dots,x_t$ to a single SAT-instance $y$ of size $poly(\max |x_i|)$ such that $y$ is satisfiable if and only if all $x_i$ are satisfiable.

My question is: Is $t$ treated as constant?

Another paper gives related definition, explicitly stating that the strong AND compression must be independent of $t$. .

  • $\begingroup$ t is obviously arbitrary $\endgroup$
    – d'alar'cop
    May 31, 2014 at 14:09
  • $\begingroup$ @d'alar'cop, indeed, but in poly(max|x_i|) is t considered a constant? If t tends to infinity the degree of poly() can be made arbitrary large for sufficiently small max(x_i). $\endgroup$
    – elluser
    May 31, 2014 at 16:00
  • 1
    $\begingroup$ So long as t is less than infinity it would still be considered poly. although, indeed, with very large t, that max may take a long time to find. as I'm sure you know, poly doesn't mean fast. in poly(max...) t is just the number of formulae (so it is and isn't constant in the sense that it depends on how many formulae you give it) $\endgroup$
    – d'alar'cop
    May 31, 2014 at 17:06

1 Answer 1


Let me help you determine how you would answer your own question.

The way is to read the paper, and in particular, look at the theorems and the definitions of the notation and the assumptions. Don't just read the abstract. You have to read the whole paper.

For instance, you can look at Theorem 1.1, noticing the phrase "...for some $n$ and $t$..." -- to me, that suggests that $t$ is a constant in Theorem 1.

Or, you could look at Theorem 3.1, which explicitly mentions that $t$ is polynomial in $n$, where $n$ is the length of the SAT-instances, in the context of Theorem 3.1.

It's also often helpful to go back to the original paper that introduced the conjecture, and see how they formulated it. In this case, you can learn (from reading the introduction to the paper you link to) that Bodlaender [2] was the originator of the conjecture, and Fortnow and Santhanam [3] proved the conjecture under a certain assumption. The paper you link to (the Dell paper) might be assuming papers have read those prior work and are familiar with the technical details of the formulation of the conjecture. So, go read those papers, too.

Bottom line: you can't stop at reading just the abstract or just the first sentence of the introduction. You may have to dive into the details, and even into prior papers, to resolve questions like this. These papers are written for other researchers (who are comfortable doing all that).

  • $\begingroup$ According to answer in another question $t$ might be exponential. If so I believe the size of input is exponential, which makes the answer easily "no": cs.stackexchange.com/questions/26361/… $\endgroup$
    – elluser
    Jun 4, 2014 at 8:25

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.