3
$\begingroup$

Is there a way to show within an integer program with constant number of variables and constraints of length $poly(\log B)$ (say length $\leq10^{1000000}\log B$), it is not possible for a variable to take exactly all the square values up to a bound $B$?

If we have a sequence of such programs, as $B\rightarrow\infty$, we can get $\#P\subseteq FP/Poly$ and may be even $\#P\subseteq FP$. How can we be sure such a sequence of constant number of integer variable and constraint programs does not exist?

What joro shows below is a consequence and not a proof. Another consequence as mentioned is $\#P\subseteq FP/Poly$.

Is this related to non-existence of multiplication in Presburger arithmetic?

Posted here: https://cstheory.stackexchange.com/questions/54524/nonexistence-of-short-integer-program-sequence-which-generates-squares after a week as I have received no relevant answers other than someone here mentioning consequences whose violation is not known and may not be necessary to refute the existence of such programs. Moderators are also unwilling to remove such answers.

Improve this question
$\endgroup$
8
  • $\begingroup$ Maybe. Need more details about your integer program. $\endgroup$
    – RobPratt
    Commented Jul 14 at 23:30
  • $\begingroup$ Linear constraints and fixed number of integer variables and fixed number of constraints. Those are the details. You are defining a polyhedron in fixed number of variables and sides with one coordinate always a square.. I think this is not possible. $\endgroup$
    – Turbo
    Commented Jul 14 at 23:34
  • 1
    $\begingroup$ That is too vague of a description. The conclusion will be true for some integer programs and false for others. $\endgroup$
    – RobPratt
    Commented Jul 14 at 23:37
  • 1
    $\begingroup$ I'm also a little confused. Here's one interpretation: given an integer program and a variable $X$, consider the set $S$ of values that $X$ takes among the feasible set. (So, we're ignoring the objective function.) Then does there exist an integer program and a variable $X$ such that $S=\{z^2\} =\{0,1,4,9,16,...\}$? Is that what you're getting at? $\endgroup$
    – Bill Bradley
    Commented Jul 15 at 3:13
  • $\begingroup$ or.stackexchange.com/questions/6545/… $\endgroup$
    – RobPratt
    Commented Jul 15 at 3:41

1 Answer 1

Reset to default
6
$\begingroup$

If you can do this efficiently, you can factor integers efficiently.

Set $X-Y=N$.

If $X=u^2,Y=v^2$ then $(u^2-v^2)=(u-v)(u+v)=N$ will give the factorization of $N$.

To avoid the trivial solution, add the constraint $ 1 < X < ((N+1)/2)^2$

The question was significantly rewritten than the original version.

I think the following is counterexample to the new question:

Consider the following decision problem:

Given two $n$ bit integers $a,b$, write IP program which returns True iff $b=a^2$.

The slight modification of computing $c :=a\cdot b$ given $a,b$ with constant number of variables might be of practical importance for multiplying large integers on conventional computer.

Improve this answer
$\endgroup$
10
  • $\begingroup$ To spell out an important detail, if $M$ is a large odd number then taking $N=M$ doesn't work, because $u-v = 1$ gives a trivial solution, but taking $N=2M$ does work because $u-v=2$, $u+v = M$ runs into parity problems. $\endgroup$
    – Peter Taylor
    Commented Jul 15 at 11:51
  • $\begingroup$ @PeterTaylor Indeed, there are some other constraints on X,Y to be added. $\endgroup$
    – joro
    Commented Jul 15 at 12:04
  • $\begingroup$ Sure.. factoring was the reason for the question... it is obvious one can factor. Indeed one can show #P is in FP if this is true. So it seems there should be a proof for the O(1) case. $\endgroup$
    – Turbo
    Commented Jul 15 at 15:48
  • 1
    $\begingroup$ @Turbo I think unless you give bound on the solution, there is no way to describe such infinite set with linear constraints. But even with a bound, probably solving $X Y=N$ is more integer programming friendly. $\endgroup$
    – joro
    Commented Jul 15 at 16:03
  • $\begingroup$ @joro " there is no way to describe such infinite set..." why is that? That is the question here. $\endgroup$
    – Turbo
    Commented Jul 15 at 16:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .