Theorem Prover for complexity theoretic reductions
-
04-11-2019 - |
Question
Can complexity theoretic reductions that lead to proofs of say NP completeness be formalized using an existing theorem prover such as Coq?
If so, can you provide an outline of how to formalize a simple reduction argument? I’d also appreciate pointers to the literature.
No correct solution
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange