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
Excellent introductory lecture! One note: the speaker mentions "slow" and "fast" in the context of the complexity classes which is a bit misleading (4:19). The analysis of algorithms is not concerned at what speed an algorithm is executed but the number of operations it makes before it halts. The algorithms solving P-complete problems are said to be "fast" because they take a small number of steps relative to (known) algorithms for NP-complete problems. Computational complexity is not about the amount of time an algorithm requires but the number of steps it makes.
Yes. It is also worth to mention that it's the "worst case". For example, think of an unsorted list of 10 random numbers. Question: Is the number "9" in the list? Best case: 1 step, because "9" could be the first element in the list. Worst case: 10 steps, because the algorithm must check all 10 elements if "9" is the last element, or if it is not in the list.
You're over complicating things, it's perfectly acceptable to talk about slow and fast in high-level discussion. Algorithms that require a large number of computational steps are slower than those that require less. Seconds taken grows with respect to operations performed.
Discrete Fourier Transform is not fast, but Fast Fourier Transform is. So your slide is wrong. You should have just said Fourier Transform was slow, but now fast.
![Chino Pacas - Modo Capone (with Drake & Fuerza Regida) [Video Oficial]](http://i.ytimg.com/vi/zjv8TQ0gBkg/mqdefault.jpg)
Great presentation. Really clear explanation.
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
thats why all quantum computers are BAWHL CRAP. do away with it from myself, id rather spend time doing more constructive things.
Excellent introductory lecture! One note: the speaker mentions "slow" and "fast" in the context of the complexity classes which is a bit misleading (4:19). The analysis of algorithms is not concerned at what speed an algorithm is executed but the number of operations it makes before it halts. The algorithms solving P-complete problems are said to be "fast" because they take a small number of steps relative to (known) algorithms for NP-complete problems. Computational complexity is not about the amount of time an algorithm requires but the number of steps it makes.
Balázs Dávid so number of halts is the amount of steps needed by an algorithm to run to completion, right?
Yes. It is also worth to mention that it's the "worst case". For example, think of an unsorted list of 10 random numbers. Question: Is the number "9" in the list? Best case: 1 step, because "9" could be the first element in the list. Worst case: 10 steps, because the algorithm must check all 10 elements if "9" is the last element, or if it is not in the list.
Balázs Dávid Thanks
You're over complicating things, it's perfectly acceptable to talk about slow and fast in high-level discussion. Algorithms that require a large number of computational steps are slower than those that require less. Seconds taken grows with respect to operations performed.
Could you name a few books/textbooks covering the subject, preferably one very beginner and one a bit more advanced? Thanks.
Very vague explanation.
Cool lecture!
how independent set takes exponential time???
Discrete Fourier Transform is not fast, but Fast Fourier Transform is. So your slide is wrong. You should have just said Fourier Transform was slow, but now fast.
i like the speaker.Cool!!
That QR code takes you to cs50/vip
You share higher than average DNA alleles with Steve Jobs
Bruh, I had this avatar for like a decade.
"mehra " sounds indian ,anyway good video !
his dad is Indian
Actually, it was his mom.
@@technolus5742 no his father sanjeev mehra
LOL i was thinking this too. Why this white guy has a Indian(Hindustani) last name :/
like your name Mehra...Sammy Mehra...
Omg, your SAT reduction diagram is a straight copypasta from Wikipedia. I thought Harvard was a good school??
whats wrong in taking reference from something reliable?
Maybe the person using it on wikepedia got it from somewhere else.0
nice :-)
P
NP
$1,000,000
Cool lecture!
how independent set takes exponential time???
How doesn't it? Does it? Doesn't it? Prove it does. Prove it doesn't.
Btw nobody knows.