-1
$\begingroup$

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.

Improve this question
$\endgroup$
  • 4
    $\begingroup$ Can you prove that your algorithm runs in polynomial time and always produces an optimal solution? $\endgroup$ – Yuval Filmus Feb 23 '20 at 1:49
  • 1
    $\begingroup$ 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). $\endgroup$ – Antti Röyskö Feb 23 '20 at 2:30
  • 1
    $\begingroup$ It's not clear what you mean by "resolve the TSP-metric". What do you mean by "show on-line"? $\endgroup$ – D.W.♦ Feb 23 '20 at 3:27
  • $\begingroup$ @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. $\endgroup$ – Ixer Feb 23 '20 at 12:17
  • 1
    $\begingroup$ @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). $\endgroup$ – dingalapadum Feb 23 '20 at 17:18
3
$\begingroup$

  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$

Improve this answer
$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Ixer Feb 23 '20 at 7:41
  • 1
    $\begingroup$ @Ixer that is exactly my point: many of the cryptographic tools rely on P != NP. If you manage to solve an NP-Complete problem in poly-time, then this solver can also be used to solve other NP-problems in polytime (like for instance breaking crypto-tools). To do this, you only need to figure out a poly-time reduction of whatever problem you are trying to solve to metric TSP, which might not be trivial but isn‘t that hard either. One basically can ‚translate‘ the crypto-problem into metric TSP, and the än use your blackbox to solve it. See en.m.wikipedia.org/wiki/Turing_reduction $\endgroup$ – dingalapadum Feb 23 '20 at 17:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.