3SAT and Establishing NP-completeness

preview_player
Показать описание
Textbooks:
Computational Complexity: A Modern Approach by S. Arora and B. Barak.
Algorithm Design by J. Kleinberg and E. Tardos.

Lecture slides by K. Wayne accompanying the latter textbook:
Рекомендации по теме
Комментарии
Автор

Great lecture, please do a video on not-all-equal 3-satisfiability (NAE3SAT)

lukemakayabu
Автор

Please, you could have done this problem completely. It would have helped me a lot.

maxpoweroverdrive
Автор

I don't think this is correct.

In your example, 3SAT could assign L_(k-1) to true and z to false.
From there, it would need to assign one of L_1 to L_(k-2) to true... even though that requirement was not in the original clause.

The arbitrary choice of z assignment puts added constraints on the clause, and that could end up causing problems in other clauses.

If you check the DPV text book, it gives a different method for transforming the input. I don't think they are logically equivalent.

bryanlozano