اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدREESSE1+ . Reward . Proof by Experiment . A New Approach to Proof of P != NP
237
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
The authors discuss what is provable security in cryptography. Think that provable security is asymptotic, relative, and dynamic, and only a supplement to but not a replacement of exact security analysis. Because the conjecture P != NP has not been proven yet, and it is possible in terms of the two incompleteness theorems of Kurt Godel that there is some cryptosystem of which the security cannot or only ideally be proven in the random oracle model, the security of a cryptosystem is between provability and unprovability, and any academic conclusion must be checked and verified with practices or experiments as much as possible. Extra, a new approach to proof of P != NP is pointed out. Lastly, a reward is offered for the subexponential time solutions to the three REESSE1+ problems: MPP, ASPP, and TLP with n >= 80 and lg M >= 80, which may be regarded as a type of security proof by experiment.
قيم البحث
اقرأ أيضاً
This document presents a simpler proof showcasing the NP-hardness of Familial Graph Compression.
Mahaneys Theorem states that, assuming $mathsf{P} eq mathsf{NP}$, no NP-hard set can have a polynomially bounded number of yes-instances at each input length. We give an exposition of a very simple unpublished proof of Manindra Agrawal whose ideas a
ppear in Agrawal-Arvind (Geometric sets of low information content, Theoret. Comp. Sci., 1996). This proof is so simple that it can easily be taught to undergraduates or a general graduate CS audience - not just theorists! - in about 10 minutes, which the author has done successfully several times. We also include applications of Mahaneys Theorem to fundamental questions that bright undergraduates would ask which could be used to fill the remaining hour of a lecture, as well as an application (due to Ikenmeyer, Mulmuley, and Walter, arXiv:1507.02955) to the representation theory of the symmetric group and the Geometric Complexity Theory Program. To this author, the fact that sparsity results on NP-complete sets have an application to classical questions in representation theory says that they are not only a gem of classical theoretical computer science, but indeed a gem of mathematics.
This paper we define a new Puzzle called Proof-of-Interaction and we show how it can replace, in the Bitcoin protocol, the Proof-of-Work algorithm.
There are several proofs now for the stability of Tooms example of a two-dimensional stable cellular automaton and its application to fault-tolerant computation. Simon and Berman simplified and strengthened Tooms original proof: the present report is a simplified exposition of their proof.
We present a very simple new bijective proof of Cayleys formula. The bijection is useful for the analysis of random trees, and we explain some of the ways in which it can be used to derive probabilistic identities, bounds, and growth procedures for s
uch trees. We also introduce a partial order on the degree sequences of rooted trees, and conjecture that it induces a stochastic partial order on heights of random rooted trees with given degrees.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
