# Does the AND-compression of SAT depends on the number of SAT instances?

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$. .

• t is obviously arbitrary – d'alar'cop May 31 '14 at 14:09
• @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). – elluser May 31 '14 at 16:00
• 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) – d'alar'cop May 31 '14 at 17:06

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.
• 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/… – elluser Jun 4 '14 at 8:25