undefined | Better HN

0 pointsguhbkji1y ago0 comments

> not even in NP

This is incorrect. Integer factorization is NP-intermediate. Very much “in NP”.

https://en.m.wikipedia.org/wiki/NP-intermediate

Also, saying factorization lacks “complexity” because sieves exist misunderstands both concepts.

> In order to talk about complexity classes such as P, NP, and co-NP, the problem has to be stated as a decision problem.

> Decision problem (Integer factorization) — For every natural numbers n and k, does n have a factor smaller than k besides 1?

> It is known to be in both NP and co-NP

https://en.m.wikipedia.org/wiki/Integer_factorization#:~:tex....

0 comments

seanhunter1y ago

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...

guhbkjiOP1y 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

keepamovin1y ago

> Integer factorization is NP-intermediate

People backing up math with wikipedia links is never a good look. Particularly when those references contradict the points they seemed they were trying to make: Since it is also true that if NPI problems exist, then P ≠ NP, it follows that P = NP if and only if NPI is empty.[your NPI reference]

So... if you've shown FACTORING is NPI then you've proven P ≠ NP, I guess, too? Hahaha! :)

1 more reply

j / k navigate · click thread line to collapse

0 pointsguhbkji1y ago0 comments

> not even in NP

This is incorrect. Integer factorization is NP-intermediate. Very much “in NP”.

https://en.m.wikipedia.org/wiki/NP-intermediate

Also, saying factorization lacks “complexity” because sieves exist misunderstands both concepts.

> In order to talk about complexity classes such as P, NP, and co-NP, the problem has to be stated as a decision problem.

> Decision problem (Integer factorization) — For every natural numbers n and k, does n have a factor smaller than k besides 1?

> It is known to be in both NP and co-NP

https://en.m.wikipedia.org/wiki/Integer_factorization#:~:tex....

0 comments

seanhunter1y ago

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."

guhbkjiOP1y 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

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

1 more reply

keepamovin1y ago

> Integer factorization is NP-intermediate

So... if you've shown FACTORING is NPI then you've proven P ≠ NP, I guess, too? Hahaha! :)

1 more reply

j / k navigate · click thread line to collapse