News for hackers. Stuff that matters.

A comment on A Polynomial Time Bounded-Error Quantum Algorithm for Boolean Satisfiability. Parent comment

Re:A Polynomial Time Bounded-Error Quantum Algorithm for Boo... by raverbashing on Wednesday July 22, 2015 @09:11AM (#9929372)
Factoring is not NP-hard (fixed!), it's simpler than that (but not, until the present day, P)

It is NP though (edited as per child comment)

[ Parent | on HN ]
Re:A Polynomial Time Bounded-Error Quantum Algorithm for Boo... by amalcon on Wednesday July 22, 2015 @09:15AM (#9929387)
It is NP (well, it would be if it were a decision problem). It is not (known to be) NP-complete (or, equivalently since it is NP, NP-hard).
[ Parent | on HN ]
Re:A Polynomial Time Bounded-Error Quantum Algorithm for Boo... by raverbashing on Wednesday July 22, 2015 @09:50AM (#9929613)
Ah true, my mistake, it is not NP-hard but it is in NP

Wikipedia says it's UP https://en.wikipedia.org/wiki/UP_%28complexity%29 (which is contained in NP)

[ Parent | on HN ]