# Showing on-line P = NP

I have developed a theorem that proposes a method to build algorithms. All the algorithms produced by this method are in P ... they never go up to more than $$6(n^{12})$$ operations.

Following that, I have defined an algorithm to resolve the TSP-metric. I agree that $$6(n^{12})$$ is a lot, but it is $$P$$ and it is the limit of n trending to infinite. For $$n < 45$$ the performance is $$5(n^9)$$.

First question: Assuming the theorem is correct, Is this enough to proof $$P = NP$$ ?

Before publishing the results and the method in a paper, I want to show on-line that the algorithm is in $$P$$. I can produce an exact result of 45 cities in less than a half of a day since the Held-Karp algorithm will need more than 16 days.

I will certify with a cloud computing provider the host hardware used, but source code will be black-boxed. Inputs will be provided by anyone and she/he/they may be the only one(s) that know(s) the solution.

Second question: Is this "show" good enough/idea to prove that I actually have solid evidence of it is not a fake?

Important to note that its purpose is only to claim attention showing evidence not substituting the proof of the theorem, I´ll make it publish (public-free) as soon as it will be demanded, I won't keep it in secret. The reason to do this "show" is that being no one if I publish the "theorem" no one gives it a chance. I have checked that way.

• Can you prove that your algorithm runs in polynomial time and always produces an optimal solution? – Yuval Filmus Feb 23 at 1:49
• By the deterministic time hierarchy theorem there are problems in $P(f(n)^2)$ not in $P(f(n))$. Note that $P(n^{24}) \subset NP$, thus there are problems in NP not solvable in $O(n^12)$. Thus there can exist no method of producing algorithms with complexity $O(n^{12})$ that works for all problems in NP (though this doesn't exclude the possibility of a $O(n^{12})$ algorithm to just TSP). – Antti Röyskö Feb 23 at 2:30
• It's not clear what you mean by "resolve the TSP-metric". What do you mean by "show on-line"? – D.W. Feb 23 at 3:27
• @AnttiRöyskö you are right the method (of the theorem) may need for some problems up to $n^{24}$ operations to produce an algorithm, and "n" is a number depending of the kernel of the problem. But when it "optimize" a boolean function it produces an algorithm that throws an exact solution with less than $6(n^{12})$ operations. – Ixer Feb 23 at 12:17
• @D.W. I think with ‚on-line’ he means putting a solver on a homepage, such that anybody could use it. On-line as in ‚putting on the internet‘. (He is not referring to an online-algorithm in the ‚usual‘ sense of the class of algorithms that aren‘t fed with the complete onput from the beginning). – dingalapadum Feb 23 at 17:18

1. Metric TSP is NP-complete - hence yes, assuming you can solve the metric TSP in $$6(n^{12})$$, this is good enough to prove $$P=NP$$.
2. Giving a blackbox that can do that, would be a quite strong evidence (if it actually works). But there are some considerations one should take into account: it actually could be somewhat dangerous, as someone else could figure out a reduction of crypto-algos to metric-TSP. It could break ‚secure communication‘, blockchain (bitcoin), etc... All these technologies are based on the assumption computer scientists and mathematicians have had for decades now, namely that that $$P \neq NP$$
• thx for your feedback. You are right about its implications, this theorem changes a lot of things. However, to resolve a hash of 512 bits it will need $6(512^10)$ (note that each bit is an independent decision) so even with a lot of supercomputers you will need more than a couple of centuries. Using quantum computers with 512 qbits you can break a hash instantaneously, with a 32 qbit one it will be broken in a few hours. – Ixer Feb 23 at 7:41