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.
"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...
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.
This! People get a bit confused by the classes: i have been. But they’re pretty simple, especially when explained like that.
Kinda funny tho we have a categorization system of problems to keep things organized and analogous, but there’s lots of confusion on how it sorts. Haha! :)
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! :)
> we’ll just have to reprioritize and update the list of algorithms we teach to undergrads, issue performance-enhancement updates to some software libraries, and patch any security vulnerabilities.
Wow, your optimism sure is something.
What are you patching and with what?
How do you “patch any security vulnerabilities” when said vulnerability is “all of our security research, except one time pad, is now so obsolete we are unsure if security based on computational complexity is at all practical anymore”?
Gosh it was early in the morning and somehow I was thinking in terms of factoring prime numbers when I added the security point. But consider cryptography as an application of number theory and compatibility theory.
Interestingly, if there are cryptography alternatives that can still be relied upon if factoring primes is easy, but the same does not hold if P = NP in a practical sense, then that’s further support for the primary point that learning more about prime numbers would not reset the foundation of number theory.
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....