4 cropped diagram
source | link

For the basics, the P vs. NP and the Computational Complexity Zoo video seems a whole lot simpler to understand.

For a computer with a really big version of a problem:

P problems

easy to solve (rubix cube)

NP problems

hard - but checking answers is easy (sudoku)

Perhaps these are all really P problems but we don't know it... P vs. NP.

NP-complete

Lots of NP problems boil down to the same one (sudoku is a newcomer to the list).

EXP problems

really hard (best next move in chess)

NP-hard problems

Edit: NP-hard isn't well explained in the video (it's all the pink bits), Wikipedia's NP-hard Euler diagram is clearer on this.

Video summary

Blackboard Euler diagrams of P, NP, NP-complete, EXP and NP-hard

Wikipedia NP-hard Euler diagram

SVG Euler diagrams of P, NP, NP-complete, and NP-hardSVG Euler diagrams of P, NP, NP-complete, and NP-hard

For the basics, the P vs. NP and the Computational Complexity Zoo video seems a whole lot simpler to understand.

For a computer with a really big version of a problem:

P problems

easy to solve (rubix cube)

NP problems

hard - but checking answers is easy (sudoku)

Perhaps these are all really P problems but we don't know it... P vs. NP.

NP-complete

Lots of NP problems boil down to the same one (sudoku is a newcomer to the list).

EXP problems

really hard (best next move in chess)

NP-hard problems

Edit: NP-hard isn't well explained in the video (it's all the pink bits), Wikipedia's NP-hard Euler diagram is clearer on this.

Video summary

Blackboard Euler diagrams of P, NP, NP-complete, EXP and NP-hard

Wikipedia NP-hard Euler diagram

SVG Euler diagrams of P, NP, NP-complete, and NP-hard

For the basics, the P vs. NP and the Computational Complexity Zoo video seems a whole lot simpler to understand.

For a computer with a really big version of a problem:

P problems

easy to solve (rubix cube)

NP problems

hard - but checking answers is easy (sudoku)

Perhaps these are all really P problems but we don't know it... P vs. NP.

NP-complete

Lots of NP problems boil down to the same one (sudoku is a newcomer to the list).

EXP problems

really hard (best next move in chess)

NP-hard problems

Edit: NP-hard isn't well explained in the video (it's all the pink bits), Wikipedia's NP-hard Euler diagram is clearer on this.

Video summary

Blackboard Euler diagrams of P, NP, NP-complete, EXP and NP-hard

Wikipedia NP-hard Euler diagram

SVG Euler diagrams of P, NP, NP-complete, and NP-hard

3 link to the euler diagram
source | link

For the basics, the P vs. NP and the Computational Complexity Zoo video seems a whole lot simpler to understand.

For a computer with a really big version of a problem:

P problems

easy to solve (rubix cube)

NP problems

hard - but checking answers is easy (sudoku)

Perhaps these are all really P problems but we don't know it... P vs. NP.

NP-complete

Lots of NP problems boil down to the same one (sudoku is a newcomer to the list).

EXP problems

really hard (best next move in chess)

NP-hard problems

Edit: NP-hard isn't well explained in the video (it's all the pink bits), Wikipedia's NP-hard Euler diagram is clearer on this.

Video summary

Blackboard Euler diagrams of P, NP, NP-complete, EXP and NP-hard

Wikipedia NP-hardWikipedia NP-hard Euler diagram

SVG Euler diagrams of P, NP, NP-complete, and NP-hard

For the basics, the P vs. NP and the Computational Complexity Zoo video seems a whole lot simpler to understand.

For a computer with a really big version of a problem:

P problems

easy to solve (rubix cube)

NP problems

hard - but checking answers is easy (sudoku)

Perhaps these are all really P problems but we don't know it... P vs. NP.

NP-complete

Lots of NP problems boil down to the same one (sudoku is a newcomer to the list).

EXP problems

really hard (best next move in chess)

NP-hard problems

Edit: NP-hard isn't well explained in the video (it's all the pink bits), Wikipedia's NP-hard Euler diagram is clearer on this.

Video summary

Blackboard Euler diagrams of P, NP, NP-complete, EXP and NP-hard

Wikipedia NP-hard Euler diagram

SVG Euler diagrams of P, NP, NP-complete, and NP-hard

For the basics, the P vs. NP and the Computational Complexity Zoo video seems a whole lot simpler to understand.

For a computer with a really big version of a problem:

P problems

easy to solve (rubix cube)

NP problems

hard - but checking answers is easy (sudoku)

Perhaps these are all really P problems but we don't know it... P vs. NP.

NP-complete

Lots of NP problems boil down to the same one (sudoku is a newcomer to the list).

EXP problems

really hard (best next move in chess)

NP-hard problems

Edit: NP-hard isn't well explained in the video (it's all the pink bits), Wikipedia's NP-hard Euler diagram is clearer on this.

Video summary

Blackboard Euler diagrams of P, NP, NP-complete, EXP and NP-hard

Wikipedia NP-hard Euler diagram

SVG Euler diagrams of P, NP, NP-complete, and NP-hard

2 reworked NP-hard description
source | link

For the basics, the P vs. NP and the Computational Complexity Zoo video seems a whole lot simpler to understand.

For a computer with a really big version of a problem:

P problems

easy to solve (rubix cube)

NP problems

hard - but checking answers is easy (sudoku)

Perhaps these are all really P problems but we don't know it... P vs. NP.

NP-complete

Lots of NP problems boil down to the same one (sudoku is a newcomer to the list).

EXP problems

really hard (best next move in chess)

NP-hard problems

really really hardEdit: NP-hard isn't well explained in the video (if the answer is 42, what'sit's all the questionpink bits), Wikipedia's NP-hard Euler diagram is clearer on this.

Video summary

enter image description hereBlackboard Euler diagrams of P, NP, NP-complete, EXP and NP-hard

Wikipedia NP-hard Euler diagram

SVG Euler diagrams of P, NP, NP-complete, and NP-hard

For the basics, the P vs. NP and the Computational Complexity Zoo video seems a whole lot simpler to understand.

For a computer with a really big version of a problem:

P problems

easy to solve (rubix cube)

NP problems

hard - but checking answers is easy (sudoku)

Perhaps these are all really P problems but we don't know it... P vs. NP.

NP-complete

Lots of NP problems boil down to the same one (sudoku is a newcomer to the list)

EXP problems

really hard (best next move in chess)

NP-hard problems

really really hard (if the answer is 42, what's the question)

enter image description here

For the basics, the P vs. NP and the Computational Complexity Zoo video seems a whole lot simpler to understand.

For a computer with a really big version of a problem:

P problems

easy to solve (rubix cube)

NP problems

hard - but checking answers is easy (sudoku)

Perhaps these are all really P problems but we don't know it... P vs. NP.

NP-complete

Lots of NP problems boil down to the same one (sudoku is a newcomer to the list).

EXP problems

really hard (best next move in chess)

NP-hard problems

Edit: NP-hard isn't well explained in the video (it's all the pink bits), Wikipedia's NP-hard Euler diagram is clearer on this.

Video summary

Blackboard Euler diagrams of P, NP, NP-complete, EXP and NP-hard

Wikipedia NP-hard Euler diagram

SVG Euler diagrams of P, NP, NP-complete, and NP-hard

1
source | link