5 ms·
> 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 fo
by curryhoward 11y ago
> 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.
- UnoriginalGuy 11y agoTo 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.
- blintzing 11y agoIs 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...
- UnoriginalGuy 11y agoHe 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.
- mmarx 11y ago> 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.
- Dylan16807 11y agok^n is exponential, not polynomial.
- Dylan16807 11y agoYes, 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.