Improving NP-complete algorithms
Suppose we have an (efficient) NP-complete algorithm. I remind that proving a provable theorem isn’t an NP problem, because there are theorems whose shortest proof is of super-exponential length. However, finding a proof that is below a given “threshold” length is an NP-complete problem. Suppose our NP-complete algorithm is fixed. How to improve it’s ability […]
[ERRONEOUS] A proof of P=NP using a Merkle tree – a new version
I’ve produced a short and much elementary proof of P=NP (without an efficient algorithm presented). I sent it to a reputable CS journal and insofar there were no errors noticed by the editor. Here is an updated version of my proof with some errors corrected: p=np-merkle.pdf In more details (and some errors corrected): Yet a […]
[ERRONEOUS] A proof of P=NP using a Merkle tree
I denote s(X) the size of data X (in bits). I denote execution time of an algorithm A as t(A,X). Using a Merkle tree technology similar to one of the Cartesi crypto (but with a true random number generator, and possibly the size of hashes themselves growing logarithmically), the size of the data and time […]
What if somebody discovers and publish an efficient P=NP solution
Lemme model what happens if somebody finds an efficient NP-complete algorithm. In layman terms (you are now studying things like this in the university, so you will soon know the formulas) an efficient NP-complete algorithm is: an algorithm that reaches any given decision accomplishment if what “to accomplish” is exactly (mathematically) described and is accomplishable […]
I’ve Proved Constructivity of P=NP
I’ve found (and proved) an algorithm that is NP-complete in the assumption that P=NP. In other words, if P=NP has a positive solution, my algorithm is its solution. I was kinda afraid if I already have almost solved P=NP as an easy consequence of my today’s things. For better or worse, no: The only theorems […]