Skip to content
Hallway
0:00 / 0:00

#pvsnp#computationalcomplexity#turingmachine

Beyond Computation: The P vs NP Problem - Michael Sipser

PoincareDuality

14K subscribers • 1 video on Hallway

YouTube
  • Recommended by 1 person: 1 in engineering communities.
  • Presented by Michael Sipser, Professor of Applied Mathematics at MIT

Intermediate. Assumes working knowledge.

170K views14 years ago1 recommendation

Computer scienceComputation and complexityAlgorithms

Michael Sipser explains the history, significance, and mathematical foundations of the P vs NP problem.

Beyond Computation: The P vs NP Problem Michael Sipser, MIT Tuesday, October 3, 2006 at PM Harvard University Science Center — Hall B One Oxford Street, Cambridge, MA, 02138 In a remarkable 1956 letter, the great logician Kurt Gödel asked the famous mathematician and computer pioneer John von Neumann whether certain computational problems could be solved without resorting to brute force search. claymath.org/public_lectures/sipser_poster.jpg claymath.org/public_lectures/sipser1.php

Why it's here

1 person recommends this

What people say. Recommended as an excellent public lecture explaining the P vs NP problem.

u/draconisin r/compsci • Recommends

Public lecture on P vs NP by Michael Sipser (2006)
117View on Reddit

u/umib0zuin r/compsci • Mentions

On “Computer Science related movies”

Would you also consider some youtube videos? I got more interested in computer science after watching Sipser talk about P vs NP. Complexity Theory is fascinating and that video should be accessible to high school students. I also liked the Komolgorov Complexity and Music video.
3View on Reddit

u/Audacein r/compsci • Mentions

On “P vs NP for beginners?”

Here is the best video i've seen on the matter : The P vs NP problem - Michael Sipser. He makes it really easy to understand.
2View on Reddit

u/FuschiaKnightin r/compsci • Mentions

On “What is NP-Hard?”

Although this doesn't address what NP-Hard is directly, it's a more general introduction to P vs. NP. Also, Sipser is a pretty cool guy! link to this video edit: I said intro to Complexity, but really just intro to P vs. NP
1View on Reddit

u/umib0zuin r/compsci • Mentions

On “What's the best computer science paper, you've ever read?”

Not really a paper but this video basically changed my perspective in programming and seriously got me interested in theoretical computer science.
1View on Reddit

u/FuschiaKnightin r/compsci • Mentions

On “Interview on Wednesday, and am a little nervous!”

I gotchu! link to this video
1View on Reddit