Professor Avi Wigderson on the "P vs. NP" problem

Avi Wigderson is a professor of Mathematics at the Institute for Advanced Study in Princeton. After studying Computer Science at Technion in Haifa, he obtained his PhD in 1983 from Princeton University. He held then various visiting positions including IBM Research at San Jose, MSRI Berkeley, and IAS Princeton. From 1986 to 2003 he was associate professor at the Hebrew University in Jerusalem. Wigderson has been for two decades a leading figure in the field of Mathematics of Computer Science, with fundamental contributions, in particular in Complexity Theory, Randomness, and Cryptography. He has been invited speaker at ICM in Tokyo (1990), and Zurich (1994), and plenary speaker in Madrid (2006). Among many awards he received both the Nevanlinna Prize (1994), and the Gödel Prize (2009).
This lecture about efficient computation, internet security, and the limits to human knowledge was hold on 7 May 2012 at ETH Zurich, when Avi Wigderson was invited as guest speaker of the Wolfgang Pauli Lectures. The Wolfgang Pauli Lectures are an annual lecture series that is devoted alternately to physics, mathematics and biology. They are named after the great theoretical physicist and Nobel laureate Wolfgang Pauli, who was professor at ETH Zurich from 1928 until his death in 1958.

[@josephfatur1747]

AW's is the only good explanation I've come across. Nice !

[@medadrufus]

Excellent series of lectures

[@StreamlineCarry]

Thank you very much for posting this. It is an awesome lecture!

[@jjames1977]

But there's still the question. What if there's a halting tester which works on all but a small class of problems, on which it says, correctly, "Aha, that would lead to a paradox."

[@joen.8668]

P = NP P - NP = 0 P(1 - N) = 0 P = 0, N = 1 NP = N × P = 1 × 0 = 0 Thus, P = NP Q.E.D.

[@patarnababan6440]

Congratulation. Go hurry for your 1 million dollar dude.

[@ESEJERITO]

pudiera medirse con matemáticas vectoriales como la de los poliedros en otra di mención multiplicado por el numero de posibles cara frac-tales dividido por el posible tiempo elevado a la masa del objeto. ¿?

[@frankvega5473]

P versus NP is considered one of the great open problems of science. This consists in knowing the answer of the following question: Is P equal to NP? This incognita was first mentioned in a letter written by John Nash to the National Security Agency in 1955. Since that date, all efforts to find a proof for this huge problem have failed. I show a solution to that problem as follows: Given a number x and a set S of n positive integers, MINIMUM is the problem of deciding whether x is the minimum of S. We can easily obtain an upper bound of n comparisons: find the minimum in the set and check whether the result is equal to x. Is this the best we can do? Yes, since we can obtain a lower bound of (n - 1) comparisons for the problem of determining the minimum and another obligatory comparison for checking whether that minimum is equal to x. A representation of a set S with n positive integers is a Boolean circuit C, such that C accepts the binary representation of a bit integer i if and only if i is in S. Given a positive integer x and a Boolean circuit C, we define SUCCINCT-MINIMUM as the problem of deciding whether x is the minimum bit integer which accepts C as input. For certain kind of SUCCINCT-MINIMUM instances, the input (x, C) is exponentially more succinct than the cardinality of the set S that represents C. Since we prove that SUCCINCT-MINIMUM is at least as hard as MINIMUM in order to the cardinality of S, then we could not decide every instance of SUCCINCT-MINIMUM in polynomial time. If some instance (x, C) is not in SUCCINCT-MINIMUM, then it would exist a positive integer y such that y < x and C accepts the bit integer y. Since we can evaluate whether C accepts the bit integer y in polynomial time and we have that y is polynomially bounded by x, then we can confirm SUCCINCT-MINIMUM is in coNP. If any single coNP problem cannot be solved in polynomial time, then P is not equal to coNP. Certainly, P = NP implies P = coNP because P is closed under complement, and therefore, we can conclude P is not equal to NP. You could read the details in the link below… hal.archives-ouvertes.fr/hal-01509423/document

[@markcarey67]

whether NP = P may well depend on our definition of computation we already know that quantum computers can in principle factor large numbers in very little time (Shor algorithm)

[@Zenovarse]

It poses a similar problem, whether a universal quantum computer can efficiently simulate an arbitrary physical system.

[@Eagle-jo8cx]

I study Computer Science and I have noticed that the more advance the topic is, the worse the design of the website/presentation gets 😂😂 yellow text with comic sans font on a blue background come on 😂

[@Zenovarse]

Yes. It tells us how to get good at compsci and maths. Simply make work messy and handwriting unintelligible and abstract away all the design.

[@bthdimension]

The guy may know a lot about maths and IT but absolutly nothing about design ^^

[@MrGodzylla]

it look like the Plank wall. it is easier to understand. if i can, he is too much looking for on the way to use P=PN and forget the only philosophy of it.

[@sb.sb.sb.]

exactly

[@GregShubert]

Between 25:30 and 27:00, the product 193707721 * 761838257287 is 147573952589676412927, with 9 in the billions place, not 8. Does not affect his argument.

[@ThinkTank255]

I completely disagree with the presenter assertion that P =/= NP is a good thing. Cryptography and security are VERY bad for humanity because if we do discover that P = NP then our economy will come to a halt. And, contrary to what the presenter asserts, I strongly believe (based on studying and work I have done) that P = NP, and biology (especially the human brain) is evidence of this. He simply dismissed this idea with his silly joke about putting biology into our laptop.

[@kyulangk]

Did you achieve anything new about the problem P vs NP ?

[@uga5535]

This is not true. P is defined as the class of languages that can be decided by a deterministic polynomial-time Turing machine. So the computational model is an inherent part of that definition and cannot simply be changed. Of course, you may define quantum analogues of these classes, for example BQP, which may (and, as you rightly claim, is suspected to) be more powerful than P.

[@jakejanuzelli1874]

Technically, but basically everyone assumes the Church Turing Thesis (en.wikipedia.org/wiki/Church-Turing_thesis), of which quantum computers are the only suspected counterexamples. Other than that any "reasonable" computational model you assume will be equivalent to Turing Machines.

[@GenericInternetter]

ANYONE WHO USES COMIC SANS FOR ANYTHING OTHER THAN KIDS BIRTHDAY INVITATIONS IS QUESTIONABLE gave up at 0:55

[@javiergilvidal1558]

You may have a point, the choice of lettering is childish and unfortunate, but in this case you are wrong. Widgerson may have bad taste designing his Power Points, but his contributions to scientific computing are impressive. Just check these nine papers: Saks & Wigderson 1986 Probabilistic Boolean Decision Trees and the Complexity of Evaluating Game Trees. In Proceedings of the 27th Annual IEEE Symposium on Foundations of Computer Science, pages 29-38, Toronto, Ontario, 1986. Karchmer & Wigderson, Monotone Circuits for Connectivity Require Superlogarithmic Depth, Proceedings of the 20th Annual Acm Symposium on Theoy of Computing, 539-550, 1988. Raz & Wigderson, Monotone Circuits for Matching Require Linear Depth, Proceedings of the 22nd Annual a Cm Symposium on Theory of Computing, 287-292, 1990. Histad, Wigderson, Composition of the Universal Relation, Manuscript, 1991. Karchmer, Raz, Wigderson. On Proving Super-Logarithmic Depth Lower Bounds Via the Direct Sum in Communication Complexity, Proceedings of the Sixth Annual Conference on Structure in Complexity Theory, 1991. Wigderson 2006. P, NP & Mathematics: a Computational Complexity Perspective. School of Mathematics, Institute for Advanced Study, Princeton. Luby & Wigderson 2006. Pairwise Independence and Derandomization. Foundations and Trends in Theoretical Computer Science, Vol. 1, No 4 (2006) pp. 237-301 (sic). Håstad & Wigderson 2007. The Randomized Communication Complexity of Set Disjointness. Theory of Computing, 3(11):211-219. Chen, Kayal & Wigderson 2011. Partial Derivatives in Arithmetic Complexity and Beyond. Foundations and Trends in Theoretical Computer Science, Vol. 6, Nos 1-2 (2011) pp. 1-138. This guy certainly knows what he's talking about!

[@readyplayersid]

If you decide things based on Comic Sans, then you'll skip a lot of Computer Science presentations. CERN researchers love to use Comic Sans - www.theverge.com/2012/7/4/3136652/cern-scientists-comic-sans-higgs-boson

[@trdi]

I wonder what could be said about someone using caps.

[@TheFepe20]

Okay, so check out the prize he got today...

[@Kalumbatsch]

@@trdi LOL burn

[@Serfuzz]

Anyone else click this away after a minute because of the slides design

[@AshishKumar-jj7yw]

Nope. We don’t care about these things.

[@slimshadow777]

mathmatically easy practicaly impossible

[@mbengiepeter965]

slimshadow777 if P was equal to NP then we will use that same algorithm to solve all the other 6 questions. The P versus NP question is the most important of the 7 problems