Beyond Computation: The P versus NP question (panel discussion)
Вставка
- Опубліковано 6 чер 2024
- Richard Karp, moderator, UC Berkeley
Ron Fagin, IBM Almaden
Russell Impagliazzo, UC San Diego
Sandy Irani, UC Irvine
Christos Papadimitriou, UC Berkeley
Omer Reingold, Microsoft Research
Michael Sipser, Massachusetts Institute of Technology
Ryan Williams, Stanford University
simons.berkeley.edu/events/mic...
Verifying a solution is completely unconnected to discovering a solution.
Prove it then
@@TheMusicDoctor1exactly. People love to just say these things but nobody has proven it. If you’re so sure that P does not equal NP, then prove how it’s impossible. Can’t? Ok moving on then.
The hubris of some people I stg…
What if someone figured out how to reuse time?
From who/where?
As Michael Sipser has said at 36:34, the only way to prove that P=nP is to find a new way to factorise large numbers in polynomial time. Otherwise, forget it.
Well that's obvious.
Or you can solve one of the simple NP Complete problems. Like subset sum problems, Knapsack problem etc
Factoring is not actually known to be np-complete.
It is a well-known fact that even if you show a polynomial algorithm for factoring, then this will only show that factoring belong to class P. If you want to show that P=NP, then you need to take any NP-complete problems and show that there is a polynomial algorithm for only one of them. Then this would follow that NP=P.