New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

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

Open

wimmers opened this issue Aug 19, 2020 · 0 comments

Milestone

Cook-Levin Theorem

Owner

wimmers commented Aug 19, 2020

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

wimmers added this to the Cook-Levin Theorem milestone

wimmers mentioned this issue

Implement and refine the reduction from IMP- to SAT #12

Open

maxhaslbeck mentioned this issue

IMP- to SATconstruction has polynomial blowup #21

Open

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment