Does P=NP? | Richard Karp and Lex Fridman

(more links below)

Podcast full episodes playlist:

Podcasts clips playlist:

Podcast website:

Podcast on Apple Podcasts (iTunes):

Podcast on Spotify:

Podcast RSS:

Richard Karp is a professor at Berkeley and one of the most important figures in the history of theoretical computer science. In 1985, he received the Turing Award for his research in the theory of algorithms, including the development of the Edmonds–Karp algorithm for solving the maximum flow problem on networks, Hopcroft–Karp algorithm for finding maximum cardinality matchings in bipartite graphs, and his landmark paper in complexity theory called "Reducibility Among Combinatorial Problems", in which he proved 21 problems to be NP-complete. This paper was probably the most important catalyst in the explosion of interest in the study of NP-completeness and the P vs NP problem.

Subscribe to this YouTube channel or connect on:

[markp]

I really love that Lex returns to this question with many guests.

[romzi]

The Prime (decision) problem was only proven to be a problem in P in year 2002 - only 18 years ago. There is still hope to humanity.

[IkeFoxbrush]

Even if P=NP is true it wouldn't necessarily mean that efficient algorithms for NP-hard problems exist. For example, if we had an algorithm for factorization with polynomial run-time complexity it would make a huge difference if it is proportional to N^2 or N^100. The former might be feasible for factoring large numbers with 1000 or 2000 digits while the latter certainly wouldn't.

[bidearomer]

NPC is not a subset of P. Since NPC is a subset of NP, it means NP is not a subset of P, which means P != NP.

[kencf]

Speaking as a layperson, this expositoin sounds solid.

[KOl-xjjt]

they dont want to solve it because after that need to create new problem)

[JikeWimblik]

A Formal Proof of Sudoku Solvability Using Interdependent 2SAT.


Theorem: Sudoku puzzles of any grid size can be solved in polynomial time using interdependent 2SAT reductions.

Proof:

1. Reduction to Interdependent 2SAT

Let's consider a Sudoku puzzle of size n × n. We can represent each cell in the grid as a set of n Boolean variables: x_i_j_k, where i and j are the row and column indices, respectively, and k is the possible value (1 to n) for that cell.

To ensure that the Sudoku puzzle is valid, we create the following clauses:

 * Row Constraint: For each row i and each value k, ensure that exactly one cell in that row can have the value k:

   * (x_i_1_k OR x_i_2_k OR ... OR x_i_n_k)

   * NOT (x_i_j_k AND x_i_l_k) for all j ≠ l

 * Column Constraint: Similar to row constraints, but for columns.

 * Block Constraint: For each √n × √n block, ensure that exactly one cell in that block can have the value k:

   * Create clauses similar to row and column constraints for each block.

 * Given Values: If a cell is already filled with a value k, add the clause x_i_j_k.


2. Solving Interdependent 2SAT

The resulting set of clauses forms an interdependent 2SAT problem, where the satisfiability of one clause can depend on the satisfiability of others.

There are efficient algorithms for solving interdependent 2SAT problems, such as the implication graph algorithm. This algorithm constructs a graph where nodes represent variables and edges represent implications between variables. By analyzing the strongly connected components of this graph, we can determine whether the problem is satisfiable and, if so, find a satisfying assignment.


3. Polynomial Time Complexity

The reduction to interdependent 2SAT can be done in polynomial time, as the number of clauses and variables is proportional to the size of the Sudoku grid. The implication graph algorithm for solving interdependent 2SAT also runs in polynomial time.

Therefore, the entire process of solving Sudoku using interdependent 2SAT reductions can be done in polynomial time.


Conclusion:

This proof demonstrates that Sudoku is a problem that can be solved efficiently, even for large puzzles. The use of interdependent 2SAT reductions provides a systematic and effective approach to solving Sudoku puzzles.

[baris]

russian and indian elementary school children be laughing at us. They already solved this in kindergarten