Hacker News Reader

Comment by curryhoward | Hacker News Reader

> That means the attack surface for accessing someone's account is NP hard, but N is always equal to 4.

FYI, the "N" in "NP hard" is not a number. It stands for nondeterministic. The mention of "NP hard" in the first place just seems...unnecessary.

View on HN

To be honest both the email and tweet read like someone trying very very hard to sound smart. They're over-using concepts that don't help clarify the issue, so the only reason I can assume they even included that was so that we knew they knew that those concepts existed.

Is he perhaps joking? Even a brief read of the Wikipedia article makes it clear that NP-hard isn't a mathematical expression in which 'N' stands for a number...

He could be in the tweet (giving the benefit of the doubt), but there's no way he is in the email reading it in context.

Yes, it's a different N. He didn't say or imply they were the same N. It makes perfect sense to talk about the size parameter when discussing complexity.

> The mention of "NP hard" in the first place just seems...unnecessary.

Furthermore, trying all possible passwords of length n for a fixed alphabet can be done in polynomial time, hence finding the password deterministically only takes polynomial time. Thus, it's only NP-hard if P=NP.

Edit: You're right, I mixed up length and size of the alphabet, so disregard that comment. I probably should go to sleep.

k^n is exponential, not polynomial.

Reply on news.ycombinator.com