2
$\begingroup$

The complexity of Integer Factorization is to my knowledge still an open problem, whereas deciding, whether a given integer is a prime number is known to be in $P$ and a proof is available online here: http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf

It is however not known (cf e.g. http://en.wikipedia.org/wiki/Integer_factorization ), whether the Factorization Problem is in $FP$

Question: as the optimization variant of Integer Linear Programming is $NP$ hard and the study of the polytope of the associated $LP$ versions (i.e. integrality constraints removed) plays an important role, I would appreciate references to the study of Integer Factorization Polytope

It has been indicated to me, that the $ILP$ formulation of Integer Factorization poses no difficulty and so, I would expect, that the polytope that is associated to the relaxed $LP$ version should have been studied, at least in hope of being able to demonstrate that the problem is in $P$

Improve this question
$\endgroup$
2
  • $\begingroup$ Can you include, or link to, a definition of "the integer factorization polytope"? $\endgroup$
    – Gerry Myerson
    Commented Dec 31, 2013 at 15:43
  • $\begingroup$ @GerryMyerson: I don't know whether someone has used the term before, but I understand by it the intersection of the halfspaces resembling the linear inequalities that define the restrictions of an ILP formulation of Integer Factorization. Unfortunately, I don't know whether an ILP formulation of the Factoring Problem is known (an according reference request is unanswered since 9 months), but one user suggested that it would be easy to find such a formulation, however no details were given. I have such a formulation, but sharing it on MO is not appreciated. $\endgroup$
    – Manfred Weis
    Commented Dec 31, 2013 at 16:00

0

Reset to default

You must log in to answer this question.