[novaRom]

A generator of "all primes" is pretty simple and deterministic. But you cannot simply generate next prime given only prime n without recomputing its non-trivial remainders. That means just a binary representation of a number n doesn't provide enough information to make quick answer what is the next prime. You have to pre-compute some 'pivots' first. Basically, more complexity, but it's still simple and trivial, not even in NP.

[guhbkji]

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

[seanhunter]

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

[guhbkji]

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.

[klyrs]

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.

[keepamovin]

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! :)

[keepamovin]

> 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! :)