4 ms·

"Although RSA factorization is considered to be an NP- hard problem if keys that fulfil the above conditions are used..." Isn't this incorrect? The implication

"Although RSA factorization is considered to be an NP- hard problem if keys that fulfil the above conditions are used..." Isn't this incorrect? The implication would be that quantum computers could solve NP-Complete problems in polynomial time.

misterrobot 10y ago
Not to mention that being an NP hard problem wouldn't be a strong enough property to ensure the average-case was hard, so I don't think the "considered" saves this from being incorrect...
dalke 10y ago
NP hard is defined with reference to a non-deterministic Turing machine which runs in polynomial time. A quantum computer is not a Turing machine. Yes, it can solve things in polynomial time that a Turing machine cannot do. But that doesn't mean that given problem is/isn't NP hard.
- misterrobot 10y ago
  That's not what I'm saying. I'm saying that if factoring were NP hard, by extension a quantum computer could solve NP complete problems in polynomial time (since every problem in NP is reducible to every NP hard problem, by definition [0]). That's all I'm saying... they're implying that you could reduce, say, 3SAT to factoring, which would be very very surprising. [0] https://en.wikipedia.org/wiki/NP-hardness https://en.wikipedia.org/wiki/NP-hardness
  - dalke 10y ago
    I do not believe quantum computers can solve NP hard problems in polynomial time. According to https://en.wikipedia.org/wiki/BQP#Relationship_to_other_complexity_classes https://en.wikipedia.org/wiki/BQP#Relationship_to_other_comp... , "The relation between BQP and NP is not known." ("BQP (bounded error quantum polynomial time) is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances.")
    - rlanday 10y ago
      Right, it’s not known. Although technically we don’t know for sure if classical computers can solve NP-hard problems in polynomial time either (that’s the P vs. NP problem).
kamkha 10y ago
It's definitely not proven to be correct; we definitely don't know for sure that integer factorization is in NP-hard. If I remember correctly, it's generally suspected that factorization is not NP-complete (and thus outside of NP-hard). Wikipedia has it first on their "list of problems that might be NP-intermediate", i.e. problems that are in NP but not in P or NP-hard. [0] [0] https://en.wikipedia.org/wiki/NP-intermediate https://en.wikipedia.org/wiki/NP-intermediate
petrs 10y ago
Yes, this is an incorrect statement, sorry. It sneaked there after edits by proofreading service, but that is no excuse for us. Should be just NP. (I'm one of the authors of the paper)
- misterrobot 10y ago
  Please don't apologize, this is an excellent paper! In retrospect I feel a little bad for nitpicking, honestly -- it's a really fascinating read :)

misterrobot 10y ago

Not to mention that being an NP hard problem wouldn't be a strong enough property to ensure the average-case was hard, so I don't think the "considered" saves this from being incorrect...

dalke 10y ago

NP hard is defined with reference to a non-deterministic Turing machine which runs in polynomial time. A quantum computer is not a Turing machine. Yes, it can solve things in polynomial time that a Turing machine cannot do. But that doesn't mean that given problem is/isn't NP hard.

misterrobot 10y ago
That's not what I'm saying. I'm saying that if factoring were NP hard, by extension a quantum computer could solve NP complete problems in polynomial time (since every problem in NP is reducible to every NP hard problem, by definition [0]). That's all I'm saying... they're implying that you could reduce, say, 3SAT to factoring, which would be very very surprising. [0] https://en.wikipedia.org/wiki/NP-hardness https://en.wikipedia.org/wiki/NP-hardness
- dalke 10y ago
  I do not believe quantum computers can solve NP hard problems in polynomial time. According to https://en.wikipedia.org/wiki/BQP#Relationship_to_other_complexity_classes https://en.wikipedia.org/wiki/BQP#Relationship_to_other_comp... , "The relation between BQP and NP is not known." ("BQP (bounded error quantum polynomial time) is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances.")
  - rlanday 10y ago
    Right, it’s not known. Although technically we don’t know for sure if classical computers can solve NP-hard problems in polynomial time either (that’s the P vs. NP problem).

kamkha 10y ago

It's definitely not proven to be correct; we definitely don't know for sure that integer factorization is in NP-hard. If I remember correctly, it's generally suspected that factorization is not NP-complete (and thus outside of NP-hard). Wikipedia has it first on their "list of problems that might be NP-intermediate", i.e. problems that are in NP but not in P or NP-hard. [0] [0] https://en.wikipedia.org/wiki/NP-intermediate https://en.wikipedia.org/wiki/NP-intermediate

petrs 10y ago

Yes, this is an incorrect statement, sorry. It sneaked there after edits by proofreading service, but that is no excuse for us. Should be just NP. (I'm one of the authors of the paper)

misterrobot 10y ago
Please don't apologize, this is an excellent paper! In retrospect I feel a little bad for nitpicking, honestly -- it's a really fascinating read :)