Issues · wimmers/poly-reductions · GitHub

Labels Milestones New issue

Cleanup IMP- to SAS+ proofs

#32

· mabdula opened

on Aug 8, 2021

Prove Memory Bound for IMP-

#31

· notiho opened

on Aug 3, 2021

Prove that SAT is NP

#26

· BilelGho opened

on Dec 7, 2020

Cook-Levin Theorem

#22

· maxhaslbeck opened

on Nov 2, 2020

·

Cook-Levin Theorem

`IMP- to SAT`construction has polynomial blowup

#21

· maxhaslbeck opened

on Nov 2, 2020

·

Translation from IMP- to SAT

`IMP- to SAT`on HOL level, functional correctness

#20

· maxhaslbeck opened

on Nov 2, 2020

·

Translation from IMP- to SAT

`IMP-` infrastructure

#17

· maxhaslbeck opened

on Nov 2, 2020

·

State Cook-Levin Theorem

Translation from NREST- to IMP-

#16

· wimmers opened

on Aug 25, 2020

·

Cook-Levin Theorem

Translation from NREST to NREST-

#15

· wimmers opened

on Aug 25, 2020

·

Cook-Levin Theorem

Define NREST-

#14

· wimmers opened

on Aug 25, 2020

·

Cook-Levin Theorem

Implement and refine the reduction from IMP- to SAT

#12

· wimmers opened

on Aug 19, 2020

·

Cook-Levin Theorem

Refine the reduction from SAT to 3-SAT

#11

· wimmers opened

on Aug 19, 2020

·