P vs. NP

Useful links:
Stephen Cook's Introduction to the problem: http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf
NP vs. P information: http://www.win.tue.nl/~gwoegi/P-versus-NP.htm . I want to note the recent proof link there refers to a proof which infact is not complete and is incorrect given what it has thus far.
About NP-completeness: http://www.fact-index.com/n/np/np_complete_1.html
Some NP-complete problems (with proof): http://www.cs.uky.edu/~lewis/cs-heuristic/text/class/more-np.html
Proof of SAT to 3-SAT: http://www.google.ca/url?sa=t&source=web&cd=2&ved=0CBkQFjAB&u...

The following video is a basic introduction to the P vs. NP problem from the theoretical computer science view. I hope this helps anybody curious about this problem. I personally consider P vs. NP an interesting problem worth venturing but, I think by it's not equal or equal nature it might be too hard to decide this question but, time will tell.

There was a proof made in August, 2010 claiming they aren't equal but, I personally found lots of holes in it, and many leading figures have found lots of flaws and missing bits in it but, thus far it is a rejected proof.

An important distinction to make is many confuse P vs. NP's properties with computability when it is actually a question related to intractability. Computability relates to the existence of Turing Machines and halting properties of theoretical machines based on the Church-Turing Thesis (in relation to Turing Degrees), while P vs. NP relates to the effectiveness of algorithms in settings based on complexity classes.


Have a beautiful day!

Note: When I refer to complexities in this video assume I am speaking about Time-Complexity not Space-Complexity.

Category:

Education

Tags:

• vs.
• np
• deterministic
• polynomial
• time
• non-deterministic
• theoretical
• computer
• science
• mathematical
• mathematics
• math
• maths
• model
• theory
• intractability
• simple
• explanation
• big
• notation
• families
• set
• theories
• foundations
• computing
• logic
• logics
• reasoning
• critical
• sciences
• formalism
• formal
• computers
• explain
• P!=NP
• P=NP
• !=

[PrivationProductions]

you're so nervous making this video its difficult to watch

[Entertainmentwf]

@PrivationProductions I don't recall being nervous when I made this video...

[PrivationProductions]

@Entertainmentwf sorry i was clamoring around the net trying to understand this, and for some reason it was frustrating me at the time.

[Entertainmentwf]

@PrivationProductions No worries :)! I honestly think people make P vs. NP too much of a confusion! For some strange reason people who I can tell haven't studied it keep confusing it with computability, which is a completely different discourse in theory of computation.

[robman8855]

could you prove P not equal NP by showing an algorithm in NP that is not in P? or are we trying to prove whether or not P is a subset of NP?... I am not very educated on the subject so my question might be stupid :P

[Entertainmentwf]

@robman8855 To show P is equal to NP, you must show that you can do an NP-complete problem can be done in polynomial time. To show P is not equal to NP, you must show there will never exist a polynomial time solution to an NP-complete problem. Typically this can be very hard, and it is difficult to say much about what can be done in either by this measure. In basic, to show they are equal, you must show you can check a solution's answer roughly about the same time to make it from scratch :).

[Xmuslim2010]

I wish if you can make more videos on P vs NP, where you explain it gradually, and use drawings, charts and more writting than just talking.

Also, would be great if you speak a bit slower and very simple english :D

Thanks

[puationstation]

complexity=simplicity ... yes, time ? gtfo

[PacRimJim]

Jroy9108: You're not stupid. You're simply ignorant of this information (like me). This video assumes a lot of mathematical background, so don't be surprised that it seems incomprehensible.

[Entertainmentwf]

@egeneral27 Awesome! Thank you :)! Have a beautiful day!

[egeneral27]

i knew it! i've seen you in campus before! lol! great video.