P vs. NP: The Biggest Puzzle in Computer Science
ฝัง
- เผยแพร่เมื่อ 11 พ.ค. 2024
- Are there limits to what computers can do? How complex is too complex for computation? The question of how hard a problem is to solve lies at the heart of an important field of computer science called Computational Complexity. Computational complexity theorists want to know which problems are practically solvable using clever algorithms and which problems are truly difficult, maybe even virtually impossible, for computers to crack. This hardness is central to what’s called the P versus NP problem, one of the most difficult and important questions in all of math and science.
This video covers a wide range of topics including: the history of computer science, how transistor-based electronic computers solve problems using Boolean logical operations and algorithms, what is a Turing Machine, the different classes of problems, circuit complexity, and the emerging field of meta-complexity, where researchers study the self-referential nature of complexity questions.
Featuring computer scientist Scott Aaronson (full disclosure, he is also member of the Quanta Magazine Board). Check out his blog: scottaaronson.blog/
Read the companion article about meta-complexity at Quanta Magazine: www.quantamagazine.org/comple...
00:00 Introduction to the P vs NP problem
02:16 Intro to Computational Complexity
02:30 How do computers solve problems?
03:02 Alan Turing and Turing Machines
04:05 George Boole and Boolean Algebra
05:21 Claude Shannon and the invention of transistors
06:22 John Von Neumann and the invention of the Universal Electronic Computer
07:05 Algorithms and their limits
08:22 Discovery of different classes of computational problems
08:56 Polynomial P problems explained
09:56 Exponential NP Problems explained
11:36 Implications if P = NP
12:48 Discovery of NP Complete problems
13:45 Knapsack Problem and Traveling Salesman problem
14:24 Boolean Satisfiability Problem (SAT) defined
15:32 Circuit Complexity Theory
16:55 Natural Proofs Barrier
17:36 Meta-complexity
18:12 Minimum Circuit Size Problem (MCSP)
- VISIT our Website: www.quantamagazine.org
- LIKE us on Facebook: / quantanews
- FOLLOW us Twitter: / quantamagazine
Quanta Magazine is an editorially independent publication supported by the Simons Foundation: www.simonsfoundation.org/ - วิทยาศาสตร์และเทคโนโลยี
Read about about "Complexity Theory’s 50-Year Journey to the Limits of Knowledge" at Quanta Magazine: www.quantamagazine.org/complexity-theorys-50-year-journey-to-the-limits-of-knowledge-20230817/
Confused Here... Please Help... ????
First Statement of Logical Facts and Action in the Video...
""A Robot arrives in a foreign land where everyone either always tells the truth or always lies. The robot reaches a fork in the road with two choices. One path leads to safety in the land of truth tellers, while the other leads to doom in the land of liars. A sentry appears. But it is unclear which group they belong too."" What question can the robot ask to determine the safe route."
Q1. Which path leads to the land of liars?
Q2. Are you a liar or a truth teller?
Q3. Which path leads to your home?
Number 3 is the videos answer to robot's quandary... But WTF? THE SENTRY COULD BE LYING AND POINTING OUT THE WRONG PATH TO HIS HOME.... SINCE HE COULD BE FROM THE LIARS GROUP.
How does the video factually, logically, conclude from the stated logic RULES prior to the tested answer... That it is SAFE to go right. Why is it safe to go right.
HELLO ?
I don't see the robot being able to correctly draw a conclusion from the facts give up to that point ?????????
So how can we move on to multiple sentries if the prior action is based on a logical fallacy ????
As a CS graduate student, the theoretical sections of the field are quite mind-bending and very profound in a way. I thnink often times people underestimate what deep insights questions in computer science can give back to the world. Thank you for showing such a nice summary of one of them!
Yes. People assume human creations are somehow unnatural, but many if not all are an interation of natures patterns. We have an innate desire to express them, or their expression is just inevitable. The further we go the more we realize we are just creating something already created. In a way, unraveling the story the universe is trying to tell us.
In Sha Allah you will solve this
I think Theoretical Computer Science is as fundamental to the nature of the reality as Physics. These days more and more physicists look at problems through the lens of information theory and computational complexity.
@@test-zg4hv Wait when did we get sex robots? Where can I buy one right now? 😅😁
@iamtheusualguy2611 Absolutely. When I started studying CS I had a hard time with mathematics and didn't see much use of all the theoretical parts. But it didn't last long until I've seen the wonders of Logic, Complexity- and Computability-Theory. I consider them the absolute highlights of my time at university, and it often felt like some kind of mathematical philosophie, so deep were the results I learnt there.
I wish more people would know about the deep wonders of theoretical computer science.
I might take a crack at this on a chalkboard while I'm working my janitor job at MIT
You would fail....
@@weqe2278just like you failed at getting the joke
Go for it, Will.
Good, Will
@@weqe2278How do you like them apples! 🍎
This video is good, but a few small details to add.
1. Solving P vs NP doesn't mean all encryption breaks overnight. RSA encryption could be broken if a polynomial algorithm is found for an np complete problem, but only if the polynomial isn't too big. Even polynomial algorithms can be unusable in practice. This is all assuming an explicit constructive proof P = NP is found. Non constructive proofs will not help solve any of the real world problems, and if it is shown P is not equal to NP, nothing will change. Even if an algorithm to break RSA is found, we can build other encryption methods using NP Hard problems like Travelling Salesman Problem (shortest path version).
2. The Travelling Salesman Problem (TSP) is NP hard in it's usual statement. It is only NP complete if you ask the question "is it possible to find a path that is shorter than a given length". If you ask the problem of finding the shortest path, this is not verifiable in polynomial time.
If TSP Shortest Path is NP-Hard due to the complexity of verifying a solution, wouldn't that render it unusable for encryption, as quick verification is a requirement?
@@TheEzypzy No. If you actually know the solution, it is easy to verify. If you do not know the actual solution, it is hard to verify if a proposed solution is actually a solution. If I know the actual shortest path, it is easy to see if someone else found the same shortest path.
What is hard is if I do not know the shortest path, but I have a pretty short path, how do I ensure it is actually shortest.
@@patrickgambill9326how do you verify(for yourself or others) the answer you claim to be correct is actually correct
yeah you're right:) Like the proof that LPs can be solved in poly time:)
Its nice to know but the algorithm is unusuable compared to the Simplex Alg:)
I think RSA is Co-NP not NP and can be solved by Shor's Algorithm in polynomial time, but more recently there have been proposals for quantum safe cryptography that use random walks in higher dimensions with secret basis vectors, I think.
Turing was brilliant and saved untold lives in WWII with his encryption work. How they treated him was horrible.
I agree with u, The Imitation Game tells it.
What? He didn't save any lives in WW2
@@bennyklabarpan7002 Many, many lives were saved because of Alan Turing and his team in breaking the Enigma code.
@@reh3884 Not at all, it just prolonged the war
@@bennyklabarpan7002 still doesn't change how much he contributed to science
So glad to see Shannon mentioned. He is massively underrated, he basically is the father of modern computers (let alone Communication and Information Theory)
If I was ever getting a tattoo, it would be the formula for entropy
His last question "Will we be able to understand the solution?" is the most profound question of all.
It reminds me of the computer "Deep Thought" in "The Hitchiker's Guide to the Galaxy" which spent generations trying to solve the problem of "Life the Universe and Everything".
After many hundreds of years it came up with the answer.....42.
But what does THAT mean ????
42 just means that author of The Hitchiker's Guide to the Galaxy ran out of ideas what to write so he thrown a dice and put down the value he got.
Exactly! Let's say that matter and energy sprout out of nothing, and both can cancel out. What made them separate to start with, and rejoin later? c? the speed of light? c can survive any black hole, but we can't appreciate the speed of light as a "thing". So 42 could be an answer but we can't understand that as a solution.
It means that the person who posed the question and the brainy computer were functional idiots. Garbage in and out. In other words, bad question, bozo.
It's always about semantics, isn't it? 💀
Im a teacher and I have to applaud your video style. It's excellent from an educational perspective with very sharp and clear visualisations and superb pace. Bravo.
This was excellent! Scott Aaronson praised it highly for accuracy but did state that it would have been improved by addressing the difference between Turing machines and circuits (i.e., between uniform and non-uniform computation), and where the rough identities “polynomial = efficient” and “exponential = inefficient” hold or fail to hold.
Clearest explanation I’ve seen. Maybe it could’ve been paced slightly slower at points but nothing a manual pause and rewind won’t fix.
I love how he says 'if humanity survives long enough'. Great reminder, we really need to do better.
I'll get right on it 😉
Best video I’ve seen in a long time. Honestly. Great, on the point presentation of distinct very important, fundamental concepts of our time
What a well constructed video. I appreciate how it went from basic Computer Science knowledge and gradually introduced higher level Computer Science topics in a simply put way.
Watching a video on advanced computer science topics and not knowing how to adjust the playback speed on youtube is making me laugh
Its mind boggling how many consistently great videos Quanta Magazine puts out frequently. Thank you for this gift to the world.
lol settle down
@@codycast no thanks
One of the best explanations of P, NP. I recalled my Theory of Computation, Information Security lectures and found it really fascinating. The insights are really cool and best explained. Thank you so much !!!
Did NOT expect a Boolean logic primer in a P versus NP video. 🎉
Phenomenal visuals and amazingly concise definition. Simply beautiful.
Thanks for this, when I took computer science classes at UTD, this was glossed over in a slide, and given maybe two sentences in the textbook.
This is an amazing video, I'm really impressed by the quality of the animations and explanations. Thank you for putting the time in to make this!
the quality of these videos is so incredible
Im an electrical engineering graduate besides understanding in electricity what really shakes me is understanding of how computer thinks. I really love it as side hobby. 😊
I briefly dabbled into this topic in a Computer arithmetic hardware implementation course that I took in grad school ( MS Microelectronics Engineering) . Mainly the part on circuit complexity ( as that was the applicable concept to the course).
It’s was a really interesting topic/course, especially the part of the course where I got to optimise a hardware implementation of an FFT algorithm on an FPGA by applying the techniques in the course.
You’re video is great. My professor was talking about this in class, and you went into so much detail. I like the parts you included with the other guy too. The back and forth was cool!
This video greatly overblows the real-world significance of P vs. NP. The question is a very theoretical one and, although it would be unintuitive to learn that P = NP, it is by no means a given that a proof of P = NP would leap down from the ivory tower and cause any direct or "overnight" effect at all on the internet, AI applications, business, cryptography, etc. For people other than academics to care, we would need to see new algorithms that are actually greatly more efficient on real-world problems than current real-world approaches are, but no such algorithm is necessarily provided by a proof in this area regardless of its conclusion.
A proof doesn't even prove that such algorithms exist. P == NP is not the same thing as P-with-very-small-exponents == NP.
It could be that the knapsack problem is in P because someone finds an O(n^10,000,000) algorithm. This would be a constructive proof that P == NP but also have essentially no practical implications.
I have discovered that some programs have parts of code of P class and parts of code of NP class. There are classes of relaxations that use heuristics that can solve some problems but with no warranty about its success or about its optimality.
2:17 study of inherent resources, such as T & S needed to solve a computational problem
woah woah, so precisely put definition. awesome.
Thank you for a great explanation of p vs np! Never got it during my computer science studies
Absolutely fascinating video, animators deserve a raise
On it ..
it's fun looking into the CSAT problem and trying to figure out exactly why you can't just assume the output to be 1 and trace it back to a random possible input combination.
It eventually comes down to these two facts:
-----------------------------------------------------------------------
1. logic gate outputs can get shared between logic gate inputs.
E.g: say, the output of an OR gate is connected to 2 (or more) AND gate inputs.
2. Logic gates AND and OR have multiple inputs mapped to their outputs. This means, they are many-to-one functions and do not have inverse functions. As a result, when you try to trace back from a given output, you have to randomly guess an input every time. This wouldn't be a problem on its own but due to our first point (logic gate outputs can get shared between logic gate inputs), when two guessed inputs end up meeting at a common output, they won't necessarily match so you end up with 1 and 0 being output value simultaneously.
And that's where the computational complexity increases drastically, because now you have to keep an account of all those common outputs branching into multiple inputs, so that your guessed inputs align when they meet there.
I think an important point to be made in the field of algorithms is that a lot of the efficiency of certain algorithms depends on input size.
Theoretically, if you have a P problem and an NP problem that solve the same problem, the P problem runs in n^200 time whereas the NP problem runs in 2^n time, if your input size is always small, say 2 or 3, then actually the NP problem is more efficient.
You can also apply this idea to just the area of P problems - for example with sorting algorithms, if we know the input size will always be very small, sometimes it is more efficient to use what is learned as the “slow” algorithms (like selection sort/ bubble sort) vs the “fast” algorithms like merge sort or quicksort. Some may argue this can’t be since bubble sort runs in n^2 vs merge sort running in nlogn , so merge sort is always at least as good, however there are also hidden constants in these runtimes that get overlooked easily. You should really see the runtimes as (n^2 + c) and (nlogn + d) respectively, where c and d are constants and c < d. You can see the constants as additional overhead needed to set up the algorithm.
in academia we usually ignore the constants as n grows large, but in practice, there may be cases where n is guaranteed to be small to the point where it is actually more efficient to use the simpler “slower” algorithm. A good analogy that my professor made is why use a sledgehammer to pound in a nail when a regular hammer will do. ( this also applies to deciding which kinds of data structures to use)
Anyways nicely made video! 👍
No, it isn't.
There are some contradictory statements in your video, but it is a great presentation of N and NP problems. Thank you for creating such a wonderful explanation in layman's terms.
This was an amazing video. Thank you!
Thank you for imparting this knowledge to me.
this
is
QUANTA
truly thanks for this amazing summary!
Great quick explanation of SAT! Not as easy at it looks.
Talking about this stuff reminds me. I think the SAT Solver progress is heavily undersold. both as a technical progression, but it is really, really useful. would love a crash course. thx
Best video ever on the topics of explaining P vs NP problem
📝 Summary of Key Points:
📌 The P versus NP problem is a conundrum in math and computer science that asks whether it is possible to invent a computer that can solve any problem quickly or if there are problems that are too complex for computation.
🧐 Computers solve problems by following algorithms, which are step-by-step procedures, and their core function is to compute. The theoretical framework for all digital computers is based on the concept of a Turing machine.
🚀 Computational complexity is the study of the resources needed to solve computational problems. P problems are relatively easy for computers to solve in polynomial time, while NP problems can be quickly verified if given the solution but are difficult to solve.
🌐 The P versus NP problem asks whether all NP problems are actually P problems. If P equals NP, it would have far-reaching consequences, including advancements in AI and optimization, but it would also render current encryption and security measures obsolete.
💬 Circuit complexity studies the complexity of Boolean functions when represented as circuits, and researchers study it to understand the limits of computation and optimize algorithm and hardware design.
📊 The natural proofs barrier is a mathematical roadblock that has hindered progress in proving P doesn't equal NP using circuit complexity techniques.
🧐 Meta-complexity is a field of computer science that explores the difficulty of determining the hardness of computational problems. Researchers in meta-complexity are searching for new approaches to solve important unanswered questions in computer science.
📊 The minimum circuit size problem is interested in determining the smallest possible circuit that can accurately compute a given Boolean function.
📣 The pursuit of meta-complexity may lead to an answer to the P versus NP problem, raising the question of whether humans or AI will solve these problems and if we will be able to understand the solution.
💡 Additional Insights and Observations:
💬 "The solution to the P versus NP problem could lead to breakthroughs in various fields, including medicine, artificial intelligence, and gaming."
🌐 The video mentions the concept of computational complexity theorists wanting to know which problems are solvable using clever algorithms and which problems are difficult or even impossible for computers to solve.
🌐 The video highlights the potential negative consequences of finding a solution to the P versus NP problem, such as breaking encryption and security measures.
📣 Concluding Remarks:
The P versus NP problem is a significant conundrum in math and computer science that explores the possibility of inventing a computer that can solve any problem quickly. While finding a solution could lead to breakthroughs in various fields, it could also have negative consequences. The video discusses computational complexity, circuit complexity, and meta-complexity as areas of study that may contribute to solving this problem. The pursuit of meta-complexity raises questions about whether humans or AI will solve these problems and if we will be able to understand the solution.
Generated using Talkbud (Browser Extension)
I just saw Scott Aaronson 5 days ago (when this was released) at UT and studied P vs NP. nice timing
Okay, can we talk about how cool this animation is though??
who made the animation in this video is a genius. As well as the people behind the script!! Great job!
"Wow, imagine how many things we could do if P = NP!"
*Jevons' paradox's honest reaction:*
Great video (as always)!
Quanta is conducting a series of surveys to better serve our audience. Take our video audience survey and you will be entered to win free Quanta merchandise: quantamag.typeform.com/video
Beautiful video; thanks for sharing.
It’s not a profound problem. It’s THE most profound problem. If p =/= np, then we are essentially close to the limit and stuck until we disappear.
They got Scott Aaronson. Nice.
Beautiful work, managed to explain a very complex idea in simple terms and animation. Bravo 👏
Beautifully explained
An awesome video gave a lot of insights on the the kind of problems and it would be nice if the solutions are always used for the benefit of the society
Plain Boolean formulas cannot operate like a Turing machine because they have a fixed bound on computation (once you assign values to the variables you can simplify the expression in a fixed amount of time). For a paradigm to be Turing complete it must be possible for it to run forever, which requires conditional loops. Boolean circuits can be made Turing complete by introducing registers (for memory) and a clock to synchronize computational steps, but they can no longer be represented as pure Boolean formulas.
Such a great video, learned a lot. Can I ask what tools did you use to create such graphics and videos?
I think there's a way. Consider that there could be hidden, exploitable structures or patterns in a NP-hard problem (example) that might have less time/space complexity and depends on the input size, algorithm, the exact values/order of the input, and/or more.
Very informative! ❤
this video is GOLD
Doing one hard puzzle might take an infinite amount of time, but running an infinite amount of hard puzzles once would give you atleast ONE solution that you can verify.
Now this is my type of video
Simple things interacting can lead to complexity and emergence, this applies to algorithms...
Problems such as these are a wonderful conundrum for my little brain to twist and turn and loop around . . . . .
If P=NP that does not mean that the polynomial time solution is within reach. Polynomials of high degree also grow fast...
Nice summary
5:25 "truth circuits" are essentially analogue neural nets that cant take into account partial voltages like digital or biological nodes can to process the input layer and calculate and output.
Excellent presentation
For as long as I've known about it the "Is P - NP?" problem has intrigued me.
I do theoretical computer science research, and I found some of the explanations by the narrator in this video kinda confusing and misleading. Some things are just false. I love your videos, and before I've seen some great explanations about my area of expertise, and I was amazed by how good you manage to collect your sources to make things correct. But this one is sad :(
Could you elaborate on which parts are wrong/false?
it boggles me how many people in the comments that call themselves computer scientists call this video „the best explanation there is“ with these heavy mistakes or straight up wrong statements
@@Gin-tokiproving that proving p=np would just prove that p=np and that’s it. nothing would change overnight. it’s like saying that proving that there exists a solution for a given equation is the same as knowing the solution which is not really true. those polynomial algorithms would still have to be found and also they could be still giga slow in practice. n^10000 is still polynomial but unusable. it would be just be a theoretical result. Actually the methods to prove it would probably be even more interesting
A 20 minute video on P vs NP problems that FAILS to first define what P and NP actually stand for. Good job Quanta!
to add consistency: iff constructively solved with small constant/polynom to yield presented disruptions, PKI failure would be no factor anyway because zero-marginal cost economy/society equals non-monetary economy provided the materialized P=NP (non-deterministic processor (NDP)) is public domain, e.g., via IPFS
P=NP
Excellent & thanks.
Depending on whether or not the sentry ALWAYS tells lies, or just CAN tell lies, and whether or not you can ask multiple questions, then there can be an optimal guaranteed solution to the problem. All you have to do is ask a question with a known answer. "What is 2+2?" If they give you a false answer, then they lie, and the remaining answers just need to be inverted.
If you are limited to one question, it could be this: "If I asked the other guard which way is the safe path, what would he tell me?" Both guards would point to the unsafe route. Take the other route to safety.
I'm not sure the answer in the video is correct.
A beautiful Japanese whodunit novel called "The Devotion of Suspect X" highlights this P vs. NP problem wonderfully.
You packed so much info in and explained everything so well in under 20 minutes. Nicely done.
I'm in a bit of a confusion, in the video it's mentioned that some "seemingly" NP problems were later solved using clever polynomial algorithms which brought them back to the P problems. - (1)
But, it's also mentioned that all NP problems are equivalent and solving one would mean that N=NP and all NP problems would be theoretically solvable/computable. - (2)
In that case, comparing (1) and (2), doesn't it mean we've already sort of solved it already?
If someone can help me clear this conundrum, I'd really appreciate it. Thanks in advance :)
not all NP problems are equivalent but all NP-complete problems are equivalent, a problem is said to be NP-complete must be in NP AND Every problem in NP is reducible to it in polynomial time.
for example prime factorisation is in NP, if you find a polynomial time that solves it (wich will be a huge dicovery) does not mean P=NP because there is no known algorithm to reduce any npcomplete problem (like SAT) to prime factorization.
Ah I see, thank you so much for your response and the apt example you've provided me with.
It seems there was a misunderstanding in my part and I ended up thinking all NP problems are equivalent and didn't consider they've to be NP-complete to be equivalent to each other, and so I think to have N=NP we need to have a NP problem which is also *NP-complete* that can be solved in polynomial time.
Intuitively i would say, there always be problems that are two much dificult to computers to solve. There always will exist NP problems. Even with quantum computers, as computers arquitecture helps finding more complex solutions in polynomial time, it will always raise NP questions. Therefore its like solving all mysteries of life in computational time.
Nice. Well done.
An algorithm having polynomial time is equivalent to the following fact:
Doubling you input will multiply the processing time by a bounded amount.
Btw, great that the video only focussed on the problem itself, not the prize money.
5:13 You'll have to amend the comment on how "Boolean boolean formulas can operate like a Turing machine." There is something to be said about representation of decision problems (computably enumerable sets being Diophantine), but a fixed circuit has a maximal number of binary inputs, while an abstract Turing machine can be initialized with arbitrary size inputs.
As a mathematician and former chemical engineer, I absolutely want P=NP and practical useful algorithms to be found. Billions of important practical engineering and science problems and logistics problems need solving.
I couldn't give a shit about encryption. But it is sadly almost certain that P is not equal to NP.
just one word......."AWESOME"
Even if P vs NP has positive solution it has just an existential nature. It does not give us a way to contract polynomial-time algorithm for any NP hard ones. There are many problems for which we have the guarantee of solution's existence but yet no one could find it. So even if P VS NP solved there is no immediate danger of losing internet or bank cash.
As Knuth says, existence doesn't necessarily mean embodiment.
great explanation
So, if the universe is fundamentally quantum, then you could say that classical reality is just a subset of it that is conveniently described by p-type setups. The rest would have to be represented on a quantum computer, in quantum simulations. Or am I missing something?
Brilliant video. Think I understood nearly everything. Which says probably more about me than about your video, but still..... Thanks!😂
Jigsaw puzzles are in P btw, specifically O(n^2).
Well, proving P=NP alone wouldn't do much of what you were saying. We would still need to figure out the specific algorithms (I don't think the proof, if it exists, will also provide a template to "convert" all NP problems to P problems).
I believe the idea is that the algorithm itself is the way to prove P=NP. Another way to say it is, how could you prove P=NP without such algorithm?
Ok but what does quantum computing say about this problem?
Ok, encryption is important to everybody but the best example is the 3-body problem aka 3-body instability. When you compute the future position of three bodies subject to gravitation you'll get an answer that will always have an error. So now you are searching for an algorithm that will give you zero error. This is easy for two bodies but with three (or more) bodies one must take a time increment and compute the next position at the next time increment that is also the source of the error. Further, the 3-body systems are unstable and chaotic (have no repeating period). Nevertheless you shorten the time increment and lower the error but this will take more time to perform the computation with the result that the error reaches zero when the computing time reaches infinity. Here is a good spot to see that Turing's assertion of giving the computing machine unlimited time in his definition of the universal machine --- *it does not make it universal.*
So, ending my comment right here right now is ok and we can "seriously muse" about all this. Unfortunately the cat is out of the bag and implications are fundamental (if not existential). The thing is that our solar system is said to consist of more than two bodies. Ignoring creation/evolution the solar system will break up sooner or later and even theoretically it is now teetering on the edge and can fly apart any minute. Or you can take the 3-body instability as prime reality, chuck the solar system and figure out that the Moon is not a mass rock (hologram image?). Oh, before you call me out as a flat earther, consider that the Earth, Sun, and Moon are three bodies that are working nicely together thank you.
best one I have seen so far regarding P vs NP
Verifying a number is prime is in P (proved in 2002, Agrawal et al). A good example of a problem that regardless of being in P cannot be solved quickly. Be careful with comparing complexity classes.
thanks, I love complexity, so now I am going to research what you mean by classes of complexities!
Having studied this before I love how well explained this is for people who have no understanding of the field.
anyone who find the solution will not need the prize money
Wisdom traditions around the world have grappled with the issue.
Maybe the two scenarios has an connection to each other? Like if i have an solution or if i solved an complex problem,i would easily and more faster solve the problem.But if you had like no solution at all then it would be hard and it would take time to solve the problem? So maybe P=NP:P≠NP indicating that there's some relationship with the two scenarios?
A related question is, "What does it really mean to crack a code? " Sometimes the definition is rather artificial, such as to define "cracking" the code as meaning "taking less time to solve than brute-force iteration through every possible solution".
A more pragmatic definition would be if, say, a nuclear bomb was planted somewhere in New York City, and an encrypted message contained the exact whereabouts.
Is New York still standing? Then, yes, you really cracked the code. Is there a radioactive hole where the city used to be? Then no, you did not really crack the code.
The pragmatic and the purely theoretical perspectives may go off in different directions.
Nobody is pointing out the potential halo effect of quantum computing, that quantum computers will be able to find minimum circuits and thus design vastly more powerful classical computers. That’s probably because everyone expects quantum computers will be so unimaginably faster than even such minimized circuit designed classical computers that it won't even matter. But i suspect classical computers will act as an interface to quantum computers. And they will, at least initially, be used to solve different kinds of problems and perform different kinds of internet tasks.
Does this connect with Big O Notation and largely explain the space complexity functions deal with or are these concepts just similar?
My understanding of Big O notation is you use it to analyze algorithms by stripping away the unnecessary details and keeping the details that matter. The details that matter are what you show with Big O notation. So if you say the performance of some algorithm f with input n = n**2 + 275, the “+ 275” is really irrelevant as n gets large (the difference between 1,000 squared and 1,000 squared + 275 is trivial). So O(f) = n**2 So it is relevant because both are about the computability of an algorithm but P vs. NP describes two sets of problems with radically different performance where as big O notation is a convention for describing performance. But that’s just based on memory so I could be wrong.
There are a good chunk of standard gates, in boolean logic, but foundationally you only need 2. Not, and either and, or or. You can construct the other with these parts. Or for example is not(not A and not B) the and only returns true now if both A and B are false, meaning the whole construct becomes an or. The same trick can create and from or
The set of problems in P is smaller than the set of problems in NP - the evidence is that in most situations you can go to jail if you P where the problem is actually NP.
On circuit complexity.
Take Boolean algebra and translate it into tri part logic with logarithms. Then quad, and so on...
As a theoretical comput scientist i can tell you there is false information in this video. Like the one in 9:46 . But overall a good attempt on hard concept to grasp
Curious about the MCSP. Seems there are a lot of shortcuts an algorithm could take, ruling out entire branches of possible answers early. I don't doubt that it is NP complete but I'm not seeing why.