wimmers / poly-reductions

Polynomial-time reductions in Isabelle/HOL
2 stars 13 forks source link

Show that reduction from SAS+ to SAT is polynomial time #10

Open wimmers opened 4 years ago

wimmers commented 4 years ago

There is already a reduction from SAS+ to SAT. We need to show that it runs in polynomial time (and only incurs polynomial blowup).