I watched this over a period of two days, taking breaks. This is an amazing lecture, it was given 20 years ago and is still relevant today ! Honestly wish I had this prof as my lecturer now. The ending lines said that hopefully we will have an answer in 20 years. It's so weird to think that amount of time has passed since this was given.
D8SCOVERY UPDATE 1:07:00 online there is a paper that says "Primes is in P" so there is a polynomial time algorithm for both 1) and 2) found in 2004 indeed 3 years after that presentation. Therefore it exists a polynomial time algorithm that says if a number if either prime or composite. If it is composite however no factorization produced
P vs Np , P does not equal Np . Proff, A minus B equal X, Where X = 7,221,355,219,458,090 And where A is 1/x of B, A times B equal 1e30 …. Decision Problem**: Given the value \( X = 7,221,355,219,458,090 \), does there exist a pair of non-negative integers \( A \) and \( B \) such that \( A - B = X \) and \( A = \frac{1}{X} \cdot B \)? Verifying these conditions can be done in polynomial time, as it involves simple arithmetic operations. If there exists a subset of integers in \( S \) that sum up to \( T \) (i.e., a solution to the SUBSET-SUM instance), then the corresponding instance of your decision problem will have a solution (i.e., "yes"). Conversely, if there is no such subset summing to \( T \), then the corresponding instance of your decision problem will have no solution (i.e., "no"). Since SUBSET-SUM is NP-complete, and we have shown that SUBSET-SUM can be reduced to a decision problem, this decision problem is NP-complete. For the solution does exist with this author and can be checked with polynomial time …. For this quadratic equation is not feasible with current computational power, ChaT GPT 4/ math version does not correct give solution and can only approximate solution …. Since the problem cannot be solved correctly does suggest NP complete…. Since it could be simply checked with polynomial time, by simply Following the equation… X is given …. Does require precession mathematics beyond the scope of computational-counting-machine…
You know when you've done as much of the sudoku as you can deductively now try one more thing. In all the empty squares put a guess of 1 in the first row where it's a possibility then guess of 2 in the second row ect then do the same for columns. You should have some empty boxes with no guess or filled in. If you check your empty boxes against the numbers in the grid and in the same column and there should be 1 or 0 numbers which are left out of 1-9. If you have 1 number for your empty box which about half the empty boxes will and the row and column of the box has 1 or an even number of empty boxes in it then magically your number fits in the box.😊
**NP-complete decision problem:** Given a value for X, determine whether there exist integers A and B such that: * A - B = X * B = ln(A) This problem is NP-complete because it is a special case of the subset sum problem, which is a known NP-complete problem. **Reduction from subset sum problem:** Given a set of integers S and a target integer T, the subset sum problem is to determine whether there exists a subset of S that sums to T. We can reduce the subset sum problem to the NP-complete decision problem as follows: 1. Let S = {a1, a2, ..., an} be the set of integers and T be the target integer. 2. Create a new integer X = T + 1. 3. Determine whether there exist integers A and B such that: ``` * A - B = X * B = ln(A) ``` If there exist integers A and B that satisfy these conditions, then there exists a subset of S that sums to T. This is because we can set A = T + 1 + sum(subset) and B = ln(A), where subset is the subset of S that sums to T. Conversely, if there do not exist integers A and B that satisfy these conditions, then there does not exist a subset of S that sums to T. Therefore, the NP-complete decision problem is NP-complete. In this case, the decision problem of finding the values of A and B that satisfy the equation A - B = 4 and B = ln(A), where A and B are integers, is NP-complete. However, there do not exist any integers that satisfy this equation. Therefore, we can conclude that P does not equal NP.
The explanation presented is not a conclusive argument for solving the p=np problem. It has several flaws, including the misapplication of logarithmic functions, an unclear reduction from the Subset Sum problem, and a lack of rigorous proof for np-completeness. p=np remains one of the most important open problems in computer science, and its resolution requires a far more detailed and rigorous argument.
@@johndeere7294sure I agree, however I also assume that P vs Np is just another riddle and depending on what is being asked or how it is framed is gonna get the desired result ……. Either way the exact solution exist with the author of this post and could be simply checked “polynomial time” and simultaneously either way the amount of time for a computer to solve this is a forgone conclusion, whereby it may never find exact solution ….. Agree to disagree …..
I watched this over a period of two days, taking breaks. This is an amazing lecture, it was given 20 years ago and is still relevant today ! Honestly wish I had this prof as my lecturer now. The ending lines said that hopefully we will have an answer in 20 years. It's so weird to think that amount of time has passed since this was given.
Good to see, Today one of the professor told me about him,
A well wisher from India.
D8SCOVERY UPDATE
1:07:00 online there is a paper that says "Primes is in P" so there is a polynomial time algorithm for both 1) and 2) found in 2004 indeed 3 years after that presentation. Therefore it exists a polynomial time algorithm that says if a number if either prime or composite. If it is composite however no factorization produced
The best explanation of such complex topic. Thank you so much Vijaya!
P vs Np ,
P does not equal Np .
Proff,
A minus B equal X,
Where X = 7,221,355,219,458,090
And where
A is 1/x of B,
A times B equal 1e30 ….
Decision Problem**: Given the value \( X = 7,221,355,219,458,090 \), does there exist a pair of non-negative integers \( A \) and \( B \) such that \( A - B = X \) and \( A = \frac{1}{X} \cdot B \)?
Verifying these conditions can be done in polynomial time, as it involves simple arithmetic operations.
If there exists a subset of integers in \( S \) that sum up to \( T \) (i.e., a solution to the SUBSET-SUM instance), then the corresponding instance of your decision problem will have a solution (i.e., "yes"). Conversely, if there is no such subset summing to \( T \), then the corresponding instance of your decision problem will have no solution (i.e., "no").
Since SUBSET-SUM is NP-complete, and we have shown that SUBSET-SUM can be reduced to a decision problem, this decision problem is NP-complete.
For the solution does exist with this author and can be checked with polynomial time …. For this quadratic equation is not feasible with current computational power, ChaT GPT 4/ math version does not correct give solution and can only approximate solution ….
Since the problem cannot be solved correctly does suggest NP complete…. Since it could be simply checked with polynomial time, by simply Following the equation… X is given …. Does require precession mathematics beyond the scope of computational-counting-machine…
You know when you've done as much of the sudoku as you can deductively now try one more thing. In all the empty squares put a guess of 1 in the first row where it's a possibility then guess of 2 in the second row ect then do the same for columns. You should have some empty boxes with no guess or filled in. If you check your empty boxes against the numbers in the grid and in the same column and there should be 1 or 0 numbers which are left out of 1-9. If you have 1 number for your empty box which about half the empty boxes will and the row and column of the box has 1 or an even number of empty boxes in it then magically your number fits in the box.😊
**NP-complete decision problem:**
Given a value for X, determine whether there exist integers A and B such that:
* A - B = X
* B = ln(A)
This problem is NP-complete because it is a special case of the subset sum problem, which is a known NP-complete problem.
**Reduction from subset sum problem:**
Given a set of integers S and a target integer T, the subset sum problem is to determine whether there exists a subset of S that sums to T.
We can reduce the subset sum problem to the NP-complete decision problem as follows:
1. Let S = {a1, a2, ..., an} be the set of integers and T be the target integer.
2. Create a new integer X = T + 1.
3. Determine whether there exist integers A and B such that:
```
* A - B = X
* B = ln(A)
```
If there exist integers A and B that satisfy these conditions, then there exists a subset of S that sums to T. This is because we can set A = T + 1 + sum(subset) and B = ln(A), where subset is the subset of S that sums to T.
Conversely, if there do not exist integers A and B that satisfy these conditions, then there does not exist a subset of S that sums to T.
Therefore, the NP-complete decision problem is NP-complete.
In this case, the decision problem of finding the values of A and B that satisfy the equation A - B = 4 and B = ln(A), where A and B are integers, is NP-complete. However, there do not exist any integers that satisfy this equation.
Therefore, we can conclude that P does not equal NP.
The explanation presented is not a conclusive argument for solving the p=np problem.
It has several flaws, including the misapplication of logarithmic functions, an unclear reduction from the Subset Sum problem, and a lack of rigorous proof for np-completeness. p=np remains one of the most important open problems in computer science, and its resolution requires a far more detailed and rigorous argument.
@@johndeere7294sure I agree, however I also assume that P vs Np is just another riddle and depending on what is being asked or how it is framed is gonna get the desired result ……. Either way the exact solution exist with the author of this post and could be simply checked “polynomial time” and simultaneously either way the amount of time for a computer to solve this is a forgone conclusion, whereby it may never find exact solution ….. Agree to disagree …..