Same. I’m not wasting cycles on this bullshit.

If you skip peer review I don’t give a shit about what you “publish.”

I’m not vetting your bullshit when I write.

You are far braver than I am. I have zero interest in running that sort of bullshit on any of my machines.

Susan Collins will be disappointed in literally everyone.

I don’t think there is a limit. Let’s keep several dozen crimes in reserve for next time.

No, we don’t use it as an adjective. It is a set. That’s literally all it is.

And predicating anything on the assumption that P equals NP is rather absurd. Of course, we can’t rule it out as a possibility. But virtually nobody in the discipline believes that to be the case. And honestly, why would it be? If there were polynomial time solutions to that many problems of that degree of importance, surely we would have discovered something by now.

I’m not confused. I’ve been teaching this subject for over a decade.

I’m not certain are you arguing with me?

I was largely agreeing with you.

I had to look it up. I didn’t realize they have been around for that long.

We can actually make stronger claims about factoring. We know for certain do that it is not in NP hard, so you are correct there

And I’m not exactly a security expert, but moving away from RSA at this point makes sense. Early assumptions about the difficulty of factoring large semi-primes certainly hasn’t panned out (in particular in light of the growing risk of quantum computers.)

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 NP-complete because it is not a member of NP-hard.

You are correct that verifiability is in there, but you have to also be able to do the reduction.

There are plenty of problems out there where we lack polynomial time solutions, while the problem also lacks the expressiveness required to reduce back and forth.

We actually don’t know if integer factorization is not in P, though.

Right now, I think most of us would guess that it is a prime candidate for NP Intermediate. Hence why I mentioned it earlier.

And you absolutely can solve it in polynomial time just not with classical architectures.

really NP complete

I don’t care who you want to get in the weeds with or what you wish to spar about, you’re just not correct.

There is no almost NP complete. There are strong and weak variants, sure, and those have particular implications.

But you’re drawing conclusions that don’t exist from definitions that you clearly don’t understand.

Signed: Somebody who has taught theory of computation for over a decade.

it relies on P vs NP

That is incorrect. It relies on perceived difficulty of factoring large semi-prime. P equals NP is related, of course, if it happens to be an NP-intermediate problem, but the difficulty of factoring is not because it’s NP-complete.

There are already classical algorithms that are sub-exponential to solve the problem. If it were the case that the problem was NP-complete, then we would have had a big advance in our theory and practice based on it.

Sounds dumb, idk.