3 ms·

Factorization is indeed in NP. It might also be in P. I should've said "based on the idea that" instead of "the fact that." "Hello World" is NP. It's just not

Factorization is indeed in NP. It might also be in P. I should've said "based on the idea that" instead of "the fact that." "Hello World" is NP. It's just not useful to talk about that fact.

dcosson 16y ago
"Hello World" isn't a decision problem, but I see your point. However NP-Complete (and by extension NP-Hard) and P are distinct classes of problems, http://en.wikipedia.org/wiki/NP-complete http://en.wikipedia.org/wiki/NP-complete so my statement that factorization is not an NP-Hard problem is true (unless, of course, P=NP). Either way, my point was that there are systems (i.e. quantum computers) that can factor numbers efficiently, but it is still widely believed that true NP-Complete and NP-Hard problems cannot be solved efficiently even with such systems.
masterzora 16y ago
Alright, I've been slightly unsure with each of your replies in this thread, but this one finally convinces me that you're just good at this "April Fools" thing.
deleted 16y ago
[deleted]
bdhe 16y ago
> Factorization is indeed in NP. It might also be in P. I should've said "based on the idea that" instead of "the fact that." I'll reiterate. It is unknown if factorization is currently NP-hard. UKNOWN. It is most likely NOT NP-hard otherwise there would be huge implications in Complexity Theory. It suffices for crypto for problems to be hard on an average. Factoring a random product of two large primes is hard. Factoring is probably not NP hard because no one knows if a factoring algorithm will help solve SAT.
- presidentender 16y ago
  NP is a superset of P.
  - bdhe 16y ago
    I think I was mistaken in understanding what you said. Yes, factoring is in NP, but it is not known to be NP-hard. Being in NP doesn't automatically imply its usefulness in Crypto (because, as you say, P is a subset of NP). Neither does the NP-hardness of a problem automatically imply its usefulness. Crypto seems to need these weird problems that are not always NP-hard, yet, in some sense, harder than NP-hard problems. You can think of it as: crypto => P != NP, but not vice-versa.

Factorization is indeed in NP. It might also be in P. I should've said "based on the idea that" instead of "the fact that." "Hello World" is NP. It's just not useful to talk about that fact.

dcosson 16y ago

"Hello World" isn't a decision problem, but I see your point. However NP-Complete (and by extension NP-Hard) and P are distinct classes of problems, http://en.wikipedia.org/wiki/NP-complete http://en.wikipedia.org/wiki/NP-complete so my statement that factorization is not an NP-Hard problem is true (unless, of course, P=NP). Either way, my point was that there are systems (i.e. quantum computers) that can factor numbers efficiently, but it is still widely believed that true NP-Complete and NP-Hard problems cannot be solved efficiently even with such systems.

masterzora 16y ago

Alright, I've been slightly unsure with each of your replies in this thread, but this one finally convinces me that you're just good at this "April Fools" thing.

deleted 16y ago

[deleted]

bdhe 16y ago

> Factorization is indeed in NP. It might also be in P. I should've said "based on the idea that" instead of "the fact that." I'll reiterate. It is unknown if factorization is currently NP-hard. UKNOWN. It is most likely NOT NP-hard otherwise there would be huge implications in Complexity Theory. It suffices for crypto for problems to be hard on an average. Factoring a random product of two large primes is hard. Factoring is probably not NP hard because no one knows if a factoring algorithm will help solve SAT.

presidentender 16y ago
NP is a superset of P.
- bdhe 16y ago
  I think I was mistaken in understanding what you said. Yes, factoring is in NP, but it is not known to be NP-hard. Being in NP doesn't automatically imply its usefulness in Crypto (because, as you say, P is a subset of NP). Neither does the NP-hardness of a problem automatically imply its usefulness. Crypto seems to need these weird problems that are not always NP-hard, yet, in some sense, harder than NP-hard problems. You can think of it as: crypto => P != NP, but not vice-versa.