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?
-
-
the NSA published some of these, but it also makes reference to other letters, but it doesn't go that deep (nothing about complexity classes for instance), it proposed a cipher as well as a model for the key space anticipating the standard model https://www.nsa.gov/news-features/declassified-documents/nash-letters/assets/files/nash_letters1.pdf …
২ replies ০ টি পুনঃটুইট ১টি পছন্দ -
উত্তর দিচ্ছেনReplying to @mHaGqnOACyFm0h5 @matthew_d_green এবং অন্য
"the mean key computation length increases exponentially with the length of the key"
১ reply ০ টি পুনঃটুইট ০টি পছন্দ -
Yeah. But when you think about it, this conjecture is basically the existence of one way functions. Unfortunately he doesn’t really capture any of the implications.
২ replies ০ টি পুনঃটুইট ১টি পছন্দ -
উত্তর দিচ্ছেনReplying to @matthew_d_green @mHaGqnOACyFm0h5 এবং অন্য
Noam Nisan talks about this here: https://agtb.wordpress.com/2012/02/17/john-nashs-letter-to-the-nsa/ … Interestingly Godel in 1956 also talked about PvsNP in a letter to von Neumann
২ replies ৩ টি পুনঃটুইট ১৪টি পছন্দ -
উত্তর দিচ্ছেনReplying to @zkproofs @mHaGqnOACyFm0h5 এবং অন্য
And Godel’s description is only a little bit more complex than what Nash wrote.
২ replies ০ টি পুনঃটুইট ৩টি পছন্দ -
উত্তর দিচ্ছেনReplying to @matthew_d_green @zkproofs এবং অন্য
But then Shannon in 1949 does say a few things about complexity.pic.twitter.com/MWPTh9D7wT
২ replies ২ টি পুনঃটুইট ৭টি পছন্দ -
উত্তর দিচ্ছেনReplying to @matthew_d_green @mHaGqnOACyFm0h5 এবং অন্য
That seems like a description of security reductions in the third paragraph
১ reply ০ টি পুনঃটুইট ৩টি পছন্দ -
-
উত্তর দিচ্ছেনReplying to @matthew_d_green @zkproofs এবং অন্য
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.
৬ replies ২ টি পুনঃটুইট ২৪টি পছন্দ
Yeah. There were a lot of very interesting classified rooms. And still are.
লোড হতে বেশ কিছুক্ষণ সময় নিচ্ছে।
টুইটার তার ক্ষমতার বাইরে চলে গেছে বা কোনো সাময়িক সমস্যার সম্মুখীন হয়েছে আবার চেষ্টা করুন বা আরও তথ্যের জন্য টুইটারের স্থিতি দেখুন।