Questions tagged [cook-levin]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
6 votes
1 answer
1k views

Does the Cook-Levin theorem relativize?

My only motivation for asking this question is long-standing curiosity, but I am interested in seeing a proof (or disproof) that the Cook-Levin theorem relativizes. If you have a proof that the ...
user avatar