I keep reading all these descriptions that say John Forbes Nash Jr anticipated the P/NP problem in some letters to the NSA but other people say his conjecture was kind of obvious and basically Shannon already had it. What do you think @SteveBellovin and @mattblaze?
-
-
But then Shannon in 1949 does say a few things about complexity.pic.twitter.com/MWPTh9D7wT
-
That seems like a description of security reductions in the third paragraph
-
What percentage of modern cryptography could have been invented during the 1950s if all these people had been brought together in a room. I wonder what percentage *was* invented and it’s all still classified.
-
Also, if someone thought to invite some number theorists into the room.
-
But nobody liked those guys.
কথা-বার্তা শেষ
নতুন কথা-বার্তা -
-
-
I think the big contribution of the P/NP formulation is using deterministic vs. nondeternistic TMs to capture computation vs. verification.
-
Well here is Godel’s intuition in 1956.pic.twitter.com/RlUwbIatv0
কথা-বার্তা শেষ
নতুন কথা-বার্তা -
লোড হতে বেশ কিছুক্ষণ সময় নিচ্ছে।
টুইটার তার ক্ষমতার বাইরে চলে গেছে বা কোনো সাময়িক সমস্যার সম্মুখীন হয়েছে আবার চেষ্টা করুন বা আরও তথ্যের জন্য টুইটারের স্থিতি দেখুন।