Beyond Computation: The P versus NP question (panel discussion)

Просмотров 27 тыс.

% 331

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/michael-sipser

Опубликовано:

12 авг 2014

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 11

@Dhowlan 2 года назад

Verifying a solution is completely unconnected to discovering a solution.

@TheMusicDoctor1 11 месяцев назад

Prove it then

@spidermonkey7280 9 месяцев назад

@@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…

@sisyphus_strives5463 День назад

People like you just don't know how high the heavens are. Since you can make such a strong statement, surely you can provide a rigorous mathematical argument that this is the case?

@Freshiefunnies 2 года назад

What if someone figured out how to reuse time?

@morgengabe1 Год назад

From who/where?

@Osama30061989 6 лет назад

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.

@georgesotiriou7051 6 лет назад

Well that's obvious.

@bhagvanparge 6 лет назад

Or you can solve one of the simple NP Complete problems. Like subset sum problems, Knapsack problem etc

@grumpytroll6918 5 лет назад

Factoring is not actually known to be np-complete.

@Y_M_Alhamdan 3 года назад

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.