0
$\begingroup$

Say there is someone claiming to have solved P vs NP, by finding a (computationally feasible, i.e. no huge constants) polynomial solution to a problem in NP:

Apart from a formal proof, is there any kind of challenge comparable to the RSA Numbers, which could be used to "prove" (or at least give strong evidence) that you have indeed found a polynomial solution to a NP problem?

[For comparison: If I claim to have found a solution to FACTORING and present factors for RSA-2048, that might not actually prove my approach, but would make my attempt a lot more credible]

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ "No huge constant" is irrelevant. What matters is the asymptotic behavior. $\endgroup$
    – user16034
    Commented Sep 26, 2023 at 7:33
  • 1
    $\begingroup$ If you truly have broken the conjecture, spend the next year learning relevant proof techniques and win the gold watch. $\endgroup$
    – user16034
    Commented Sep 26, 2023 at 7:38
  • 1
    $\begingroup$ "give strong evidence" is not enough and probably unrealistic. Non-polynomial behavior is understood "in the worst-case" and we don't know intrinsically worst-case problems. An informal but correct proof could do. By the way, we already have very strong evidence that the conjecture holds. $\endgroup$
    – user16034
    Commented Sep 26, 2023 at 7:40
  • $\begingroup$ @YvesDaoust I don't think you are addressing the relevant point, which I understood as "suppose one has a practical algorithm for an NP-complete problem, can he prove that without revealing the algorithm?" $\endgroup$
    – Command Master
    Commented Sep 27, 2023 at 8:27
  • $\begingroup$ If you can find, in a bunch of previously unbroken hash functions, with independent mechanisms, a preimage to some meaningful hash string, then I believe most people will find that extremely strong evidence you have proven the non-existence of one-way functions, and perhaps even P=NP. $\endgroup$
    – Command Master
    Commented Sep 27, 2023 at 8:31

2 Answers 2

Reset to default
3
$\begingroup$

You might consider the following instance of an NP-hard problem: Eternity II. This particular instance has been unsolved for more than 15 years, despite dozens of papers about it. Solving this problem would get significant attention, and if it comes with a claim of having a polynomial time algorithm for it, people would definitely be compelled to check it.

Beating the benchmarks in any NP-hard problem, say, on datasets for TSP, or Set Cover, would also be significant enough to draw attention to the new algorithm.

Improve this answer
$\endgroup$
1
$\begingroup$

https://cgi.luddy.indiana.edu/~sabry/cnf.html

if you have a computationally-feasible program to solve SAT problems (NP-complete), but you don't know how to encode other problems into SAT, this website will encode factoring for you

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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