NP Completeness 4 - Satisfiability and 3SAT

In this video we introduce the most classic NP Complete problem -- satisfiability. We prove that 3SAT is NP Complete by reducing SAT to it.

[saakshi.padamwar]

Best explanation ever. I'm studying for my exams right now and this is the best help I could get on YouTube.

[adityapalve]

U saved me before my exam. Thks a lot.

[kiran]

So much clearer now, thank you so much!!

[solinmaaroof]

thank you for the explanation! is it possible to get these lecture notes?

[JikeWimblik]

Theorem: The proposed Sudoku solving algorithm, which utilizes a 45-grid encoding and a 2-SAT solver to iteratively identify and eliminate invalid '1' placements, has a polynomial-time complexity.
Proof:
* Sudoku Encoding and Problem Structure:
* The Sudoku puzzle is encoded using 45 grids, where each grid corresponds to a specific number (1-9) and a specific position within a 3x3 subgrid.
* Each grid contains '1's representing the presence of that number in the corresponding cells and '2's representing its absence.
* Crucially: Each grid must have exactly two '1's to satisfy the Sudoku constraints (one number appears twice within its row, column, and 3x3 subgrid). This limited capacity is key to the algorithm's efficiency.
* Algorithm Description:
a) Initialization: All possible '1' placements across all 45 grids are considered.
b) Iteration:
i. 2-SAT Solver and Invalid '1' Identification: For each grid, a 2-SAT instance is constructed based on the current '1' placements and the Sudoku constraints (row, column, and subgrid). The 2-SAT solver checks the satisfiability of these constraints. Since each grid can only have two '1's, attempting to place more will inevitably lead to an unsatisfiable instance, revealing at least one invalid '1' placement within that grid.
ii. Elimination: The identified invalid '1' placement is marked, permanently eliminating that possibility.
iii. Constraint Propagation: The information from the invalid placement is propagated to other grids, potentially identifying more invalid placements due to shared constraints (same row, column, or 3x3 subgrid).
c) Termination: The algorithm terminates when a valid solution is found, which occurs when each grid contains exactly two '1's that satisfy all Sudoku constraints.
* Why at Least One Invalid '1' is Guaranteed:
* Pigeonhole Principle: Each grid has 9 cells (pigeonholes) but can only accommodate two '1's (pigeons). If we attempt to place a '1' in every cell of a grid, we violate the "two '1's per grid" rule. By the Pigeonhole Principle, at least one cell must then contain an invalid '1'.
* Sudoku Constraints: A solvable Sudoku puzzle has a unique solution with strict constraints on where each number can be placed. Testing all possible '1's in a grid forces violations of these constraints, leading to the detection of invalid placements.
* Complexity Analysis:
* Constant Grid Size: Each grid has a constant size (9 cells).
* Guaranteed Invalid Placement: In each iteration, at least one invalid '1' placement is guaranteed to be found.
* Limited Iterations: The total number of iterations is limited by the total number of possible '1' placements across all grids (45 grids * 9 cells/grid = 405). This upper bound ensures the algorithm doesn't run indefinitely.
* Polynomial Time per Iteration: Each iteration involves:
* Constructing a 2-SAT instance (polynomial time).
* Running the 2-SAT solver (polynomial time).
* Marking the invalid placement and propagating constraints (constant time).
* Overall Complexity:
* The number of iterations is bounded by a constant (405), and each iteration takes polynomial time. Therefore, the overall complexity of the algorithm is polynomial.
Conclusion:
The proposed Sudoku solving algorithm, by leveraging the limited capacity of each grid in the encoding and the power of the 2-SAT solver to systematically identify and eliminate invalid '1' placements, guarantees finding the solution in polynomial time. This result offers a new perspective on the solvability of Sudoku and potentially has broader implications for tackling other constraint satisfaction problems.

[haythamadnan]

The link you provided is the proof of the Cook's theorem, but could you please share the link of the generic proof of reducing SAT to 3-SAT in polynomial time? Thanks!

[hjain]

Thanks for these wonderful lectures. Also can you share your notes.

[seraph]

At 14:42, couldnt you just substitute the terms Xa represents into the formula to get 3-CNF?

[underlecht]

You are cool. Thank you. Stuck on your video and very glad i found your explanation.

[ea]

So to prove 3SAT is in NP we reduce SAT to 3SAT. What if we want to prove that SAT is in NP? as far as I know every problem in NP can be reduced to the other problems. What about the first problem prove? Its like the chicken first or the egg + which one is the chicken and which one is the egg?
Thanks for the great video!

[shrutijadhav]

is it not a rule that in a clause we cant have 2 literals the same as here XA is same for last two clauses

[miarodgers]

when i plug this into a truth table, the answers are not the same. is there a reason why it would be wrong?

[craine]

Can you link the proof you mentioned in the video?