Factoring is not in any category because we don’t have a proof for it. As it stands, the algorithms we have require exponential time in the worst case, but solutions can be verified in polynomial time, which is NP-complete. I said “at most” for a reason.
Also, every algorithm is verifiable. If there’s no better way to do it then re-running the algorithm and that algorithm is exponential, then it’s NP-Hard.
Factoring is in a category. Everything computable exists somewhere. We know factoring to be in NP.
What I was disagreeing with was the “at least” and “at most” characterization of NP completeness. It is a set, not a boundary. The actual diagram of the complexity zoo is much more complicated than concentric circles.
And for verifiability, I was not referring to it as an existential sort of thing. I was simply saying that I agreed with you in that particular facet, but it isn’t sufficient to describe NP completeness. You also need NP-hardness.
Factoring is not in any category because we don’t have a proof for it. As it stands, the algorithms we have require exponential time in the worst case, but solutions can be verified in polynomial time, which is NP-complete. I said “at most” for a reason.
Also, every algorithm is verifiable. If there’s no better way to do it then re-running the algorithm and that algorithm is exponential, then it’s NP-Hard.
Factoring is in a category. Everything computable exists somewhere. We know factoring to be in NP.
What I was disagreeing with was the “at least” and “at most” characterization of NP completeness. It is a set, not a boundary. The actual diagram of the complexity zoo is much more complicated than concentric circles.
And for verifiability, I was not referring to it as an existential sort of thing. I was simply saying that I agreed with you in that particular facet, but it isn’t sufficient to describe NP completeness. You also need NP-hardness.