Computer-assisted proofs
We now have a MATLAB-assisted NP-hardness proof for our problem. We basically came up with a gadget, and could easily prove by hand that in the good case the gadget was feasible, but an NP-hardness proof clearly also requires a proof that in the bad case there's no way of doing well on the gadget. We were completely unable to prove this by hand,
( Read more... )
Comments 2
I knew Mathematica and Maple could be used to prove equalities of algebraic expressions and maybe more, although its foundations are questionable (I once met a PhD student of Alan Bundy's whose mission was to fix this).
I didn't know that Matlab could come up with anything that would be called a "proof" in the ordinarily sense.
Reply
Reply
Leave a comment