1
$\begingroup$

I have found a polynomial time solution of an NPC problem. My algorithm give exact result in most cases. For example if I run my algorithm for 20000 problem instances, then it fails 10 times to give correct result. But, I am unable to prove the approximation ratio mathematically. Is it feasible to show it with the experimental results? I am waiting to hear the possible solutions for it.

$\endgroup$
  • 1
    $\begingroup$ "I have found a polynomial time solution of an NPC problem" and "it fails 10 times" are contradictory statements. $\endgroup$ – Raphael Jul 24 '17 at 12:37
  • 1
    $\begingroup$ Fails means it is not giving exact result but near optimal. $\endgroup$ – NARAYAN CHANGDER Jul 24 '17 at 13:02
  • 1
    $\begingroup$ Yup, which means you do not have found a poly-time solution of an NPC problem. $\endgroup$ – Raphael Jul 24 '17 at 13:50
  • 1
    $\begingroup$ Oh yes its not possible and also I did not claim that I solve it using poly-time. My query is if my algorithm run in poly-time but rarely fails to give correct result but near optimal. $\endgroup$ – NARAYAN CHANGDER Jul 24 '17 at 14:08
  • 1
    $\begingroup$ 1) You should edit your answer to clarify the first sentence then. 2) Whether your algorithm has the properties you claim is impossible to say without seeing the algorithm. $\endgroup$ – Raphael Jul 24 '17 at 14:37
2
$\begingroup$

Is it feasible to show it with the experimental results?

No, you can not. There is no shortcut around formal proofs here.

$\endgroup$
1
$\begingroup$

First of all, any more information to give about the problem? Your algorithm? These sorts of things would make a question such as this far more approachable.

In what sense are you unable to prove it? I think a theoretical result is far stronger than any experimental results you may be able to gather, since it demonstrates that, without fail, your algorithm will return a solution with a value within some constant factor of the optimal for any given instance of the problem. The instances of the problem that your algorithm fails to give a answer for, do you notice any trends in terms of how 'off' the results are?

$\endgroup$

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.