undefined | Better HN

0 pointsseanhunter1y ago0 comments

That NPI wiki link says integer factorization may be in NP-intermediate iff NPI isn't an empty set, which is unknown at the current time. My understanding is the complexity of factorization is also currently an unsolved problem although no polynomial time algorithm is currently known.

Eg https://www.connellybarnes.com/documents/factoring.pdf

    "Finally, in computational complexity theory, it is unknown whether
    factoring is in the complexity class P. In technical terms, this means that
    there is no known algorithm for answering the question "Does integer N have
    a factor less than integer s?" in a number of steps that is ))(( nPO ,
    where n is the number of digits in N, and P(n) is a polynomial function.
    Moreover, no one has proved that such an algorithm exists, or does not
    exist."

That is supported by the second wiki link you provide, which has "Unsolved problem in computer science: Can integer factorization be solved in polynomial time on a classical computer?" in a box at the side. https://en.m.wikipedia.org/w/index.php?title=Integer_factori...

0 comments

guhbkji1y ago

You are conflating.

Integer factorization is unsolved and it’s decision problem is in NP.

IF’s decision problem’s complexity “may be in NP” because the question of whether P equalling NP is unknown.

Meaning IF is NP, but may well be P if P=NP. If P!=NP then IF is NP.

klyrs1y ago

No, IF is unquestionably in NP. The definition of NP is that a purported solution can be checked in polynomial time. That's it. Factorization can be verified by multiplication, in polynomial time, therefore the problem is in NP. Perhaps you're confounding NP with NPC? Recall that P is a subset of NP.

Not sure what you mean by "IF's decision problem" though. Primality is in P.

1 more reply

j / k navigate · click thread line to collapse