P versus NP (ft. Ola Svensson)
HTML-код
- Опубликовано: 21 дек 2016
- The P vs NP problem is one of the 7 Millenium prize problems. It is often regarded as the prestigious open problem of theoretical computer science. This video features Ola Svensson, Assistant Professor of the IC School at EPFL.
people.epfl.ch/ola.svensson
---------------------
P vs. NP and the Computational Complexity Zoo
• P vs. NP and the Compu...
Putting my Money where my Mouth isn't | Scott Aaronson (on Deolalikar's proof)
www.scottaaronson.com/blog/?p=456 
Наука
This video is absolutely fantastic, I enjoyed it greatly. Thank you for sharing your content.
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
An algorithm that solves any of the NP-complete problems in polynomial time would be a de facto proof that P=NP. Proving P /= NP requires showing that no such algorithm can exist. For P /= NP there is no shortcut.
Bonjour, ce serait bien de faire une vidéo sur la différence entre un ordinateur quantique et un classique.
sinon bonne vidéo
the price is too low
Is P=NP? Yes, but only if N=1 or P=0, why are people taking such a long time to solve this?
LOL Not this problem! ;-)
Very nice video as always.
Here's an article on how to compute the map coloring problem on a quantum computer :
www.dwavesys.com/sites/default/files/Map%20Coloring%20WP2.pdf
The main idea is to transform the problem into an Ising model whose most probable samples are the solution