P vs. NP – The Biggest Unsolved Problem in Computer Science

25
72



Get a free audiobook and a 30-day trial of Audible (and support this channel) at or text “upandatom” to 500 500 on your phone.

Hi! I’m Jade. If you’d like to consider supporting Up and Atom, head over to my Patreon page 🙂

Subscribe to Up and Atom for physics, math and computer science videos!

Computer Science Playlist

The Four Color Theorem

The Halting Problem

*Follow me* @upndatom

Up and Atom on Twitter:

Up and Atom on Instagram:

A big thank you to my AMAZING PATRONS!
Bob, Purple Penguin, Damien J, Gadi Shalom, Chris Flynn, Ofer Mustigman, Mikely Whiplash, Sachin Shenoy, Yana Chernobilsky, Lynn Shackelford, Richard Farrer, Adam Thornton, Dag-Erling Smørgrav, Andrew Pann, Anne Tan, Joe Court, Brandon Combs, Damien Holloway, Ayan Doss, Marcus Dentrey, John Lakeman, Jana Christine Saout, Michael Dean, Chris Amaris, Daniel McGown, Matt G, Dafne Kiyui, Broos Nemanic, John Satchell, John Shioli, Todd Loreman, Susan Jones, Lou, Hassan Sedaghat, Alan McNea, S, Daniel Eliassen, Sam Ross, Julian Engel, Shawn, Israel Shirk, Kay, Peter Walsh, Osa and Beth Fitch, Garrett Chomka, Jeff Schwarz, Josh B, Zach Tinawi, Bernard Wei, Bobby Butler, Matt Harden, Rebecca Lashua, Pat Gunn, George Fletcher, Jasper Capel, Luc Ritchie, Elze Kool, Aditya Anantharaman, Frédéric Junod, Vincent Seguin, Paul Bryan, Michael Brunolli, Ken Takahashi, Jesse Clark, Steven Wheeler, Atila Pires dos Santos, Roger Johnson, Philip Freeman, Bogdan Morosanu, KhAnubis, Jareth Arnold, Simon Barker, Shawn Patrick James Kirby, Simon Tobar, Dennis Haupt, Renato Pereira, Simon Dargaville, and Magesh.

For a one time donation, head over to my PayPal 🙂

*Animations*
Tom Groenestyn

*Music*
Epidemic Sound

Nguồn: https://sangoivon.vn

Xem thêm bài viết khác: https://sangoivon.vn/game/

25 COMMENTS

  1. Good video! You are right about the differences of orders of magnitude between P and NP problems (4:30), but are you estimating the computing speeds on about 100 ops./s? A modern desktop computer can make about 1 to 10 GFlops… That means 10^7 or 10^8 times faster than your estimates. Hence A P problem of O(n^3) with n = 100 would take less than a milissecond and an NP problem with 2^100 would take about 100 billion years to be solved.

  2. Well, I studied all that and taught it at the college level, and here's my take. Computer scientists seldom think in terms of information theory. But if you do, you can think of an algorithm as processing information at a certain rate. Since the input information rate can always be throttled down to next to nothing, there are problems that can never be computed in less than exponential time. (Actually, quantum algorithms can exploit exponential space, provided they have sufficient qubits, so who knows where that goes.)

  3. All the time i had to think about quantum computing here… Seems to me like NP-complete problems are P problems for quantum computers, but still NP-complete for normal ones… Not completely sure though because its not my profession…

  4. Wouldn't it take just one proof of a problem that isn't solvable in polynomial time to show that p isn't np?
    There are no problems proven to be impossible in p time?

    Great video! I envy your enthusiasm. haha

  5. Interesting, I disagree with the end part, about if a true NP can be solved with P, then NP=P, it just means that that particular problem was put into the wrong category in the first place. So every time you think you have solved P=NP, you've actually just found another problem that was in the wrong category. and when your 'bag' of NP is empty, it just means you haven't been looking at the 'big picture', to find a real NP
    I think a real true NP is an algorithm to write algorithms to solve NP's – as in true intelligence as opposed to AI.

    And go, noughts and crosses – who's the twit who renamed it tic-tac-toe
    – and basically my first program, on a TRS-80 back in the 1980's

  6. I believe the question shouldnt be is P = to NP. The question should be how can you make a NP problem equal to P.

  7. Kinda reminds me of my first Calculus class in college. I remember there were these problems we had to do and it was easy to know the answer just by looking at the equation and how the numbers were arrainged but you had to do these long equations and show work to get credit for answer.

  8. I'm confused with the statement at the end:
    "If you can show that 1 NP problem can be reduced to P. Therefore all NP problems can be reduced to P."

    How does that logically follow? All that would mean is that categorizing NP problems is imperfect, and therefore all NP problems have the potential to be solved in P. But how does that necessarily mean that NP problems cannot exist.

    Makes no sense. Its like saying "I accidentally identified this frog as a reptile. Therefore frogs don't exist."

  9. only certain forms of encryption would suffer from it. It's similar to the way quantum computing effects it. Anything that relies on procedure would be just fine. Stuff that relies on solving a math problem as making it difficult would be broken.

  10. except there are other ways to win the number game than getting 3 in a row like tic tac toe. 8-7 9-6 1-2-3-9 etc

  11. Nice video, one comment about the job interview question. Most of these kinds of sorting optimizations, work in opposition to the available memory. So the number of inputs would be very limited, while it would be fast, it may require more bits of ram, then atoms in the known universe.

LEAVE A REPLY

Please enter your comment!
Please enter your name here