News for hackers. Stuff that matters.

A comment on The Million-Key Question: Investigating the Origins of RSA Public Keys. Parent comment

Re:The Million-Key Question: Investigating the Origins of RS... by dalke on Wednesday August 10, 2016 @09:16PM (#12265764)
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.

[ Parent | on HN ]
Re:The Million-Key Question: Investigating the Origins of RS... by misterrobot on Wednesday August 10, 2016 @09:41PM (#12265855)
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

[ Parent | on HN ]
Re:The Million-Key Question: Investigating the Origins of RS... by dalke on Wednesday August 10, 2016 @10:38PM (#12266021)
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_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.")

[ Parent | on HN ]
Re:The Million-Key Question: Investigating the Origins of RS... by rlanday on Wednesday August 10, 2016 @11:04PM (#12266102)
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).
[ Parent | on HN ]