Artículo: Proving Correctness of Problem Reductions Using Dafny
Archivos
Fecha
Editor
Publicado en
Licencia Creative Commons
Resumen
Dafny is a programming language that allows users to check the correctness of their code. This requires a formal specification of what a program is expected to do, and a mechanism to prove that the actual behavior of the program satisfies the specification. The way Dafny proves correctness is by invoking the SMT solver called Z3. This means that Dafny can be used just like any other theorem prover, no matter if they are interactive like Isabelle or Coq, or non-interactive like Vampire. Our intention is to explore how effective Dafny is at proving the correctness of reductions between two decision problems. A reduction typically involves transforming one problem into another in such a way that an algorithm solving the second problem can be used to solve the original one. We are particularly interested in determining whether Dafny is suitable for proving the correctness of such reductions.


