Factoring as the problem of quadratic minimization

[tetramur]

The factoring is trivially equivalent to following minimization problem:
Minimize x1*x2 with these conditions:
x1*x2 >= N
2 <= x1 <= N-1
2 <= x2 <= N-1
x1 <= x2
Question: is it possible to get polynomial-timed solution for this problem?

[charybdis]

Originally Posted by tetramur

Minimize x1*x2 with these conditions:
x1*x2 >= N
2 <= x1 <= N-1
2 <= x2 <= N-1
x1 <= x2

Okay, let's try this. Suppose I want to factorize N = 91. I'll plug your conditions into my magic optimization machine, and out come the factors:

x1 = √91, x2 = √91

Wait, you wanted the solutions to be integers? Well, you're out of luck - my machine doesn't know how to solve that type of problem in polynomial time.

[R. Gerbicz]

Originally Posted by tetramur

The factoring is trivially equivalent to following minimization problem:
Minimize x1*x2 with these conditions:
x1*x2 >= N
2 <= x1 <= N-1
2 <= x2 <= N-1
x1 <= x2
Question: is it possible to get polynomial-timed solution for this problem?

No, you need also that x1 and x2 are integers(!), and with this it is an integer optimization problem [without easy 'shortcuts"], you can try it out using say GLPK (it is free). And it is quite well known. Another similar form:
minimize 0
subject to:
x1 and x2 are integers
x1*x2=N
2<=x1
2<=x2
ps. note that if N is prime then this form has no solution.

[tetramur]

Originally Posted by R. Gerbicz

No, you need also that x1 and x2 are integers(!), and with this it is an integer optimization problem [without easy 'shortcuts"], you can try it out using say GLPK (it is free). And it is quite well known. Another similar form:
minimize 0
subject to:
x1 and x2 are integers
x1*x2=N
2<=x1
2<=x2
ps. note that if N is prime then this form has no solution.

Yes, exactly. I intended solution to be integers.
Also, I checked that integer optimization problems are NP-complete in general, but I don't know if this particular problem is NP-complete.