View Single Post
Old 2018-07-25, 16:04   #5
chris2be8's Avatar
Sep 2009

88016 Posts

By IFP I assume you mean the Integer Factorization Problem. But exactly what do you mean by that?

Are you asking if it's in P (solvable in polynomial time) or not?

If it is do you want to know how to solve it?

If it's not in P do you want a proof it's in NP (takes an exponential function of the length of the number)? Or could it be of intermediate difficulty?

AFAIK it's not NP-complete because it can be solved in probably polynomial time by a quantum computer running Shor's algorithm. So if IFP is NP-complete a quantum computer can solve any NP-complete problem which is unlikely.

chris2be8 is offline   Reply With Quote