guhbkji (u/guhbkji) - Readit News

guhbkji commented on Breakthrough a step toward revealing hidden structure of prime numbers science.org/content/artic... · Posted by u/igitur

seanhunter · a year 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...

guhbkji · a year 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.

guhbkji commented on Breakthrough a step toward revealing hidden structure of prime numbers science.org/content/artic... · Posted by u/igitur

novaRom · a year ago

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 · a year ago

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

guhbkji commented on Breakthrough a step toward revealing hidden structure of prime numbers science.org/content/artic... · Posted by u/igitur

odyssey7 · a year ago

Yes, it’s difficult to predict where such an understanding might lead. If it reframes and redefines all of number theory, then we might call it one component of the foundational theory of number theory.

Analogously, if someone proves that P = NP, then that will be great, but the significance of lambda calculus and Turing completeness will remain. If the proof is constructive and practical, 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. Otherwise, we’ll only need to change a chapter or two in the Theory of Computation courses that universities are increasingly deprioritizing.

guhbkji · a year ago

> if someone proves that P = NP

> 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”?