Computational complexity

Concetti di Informatica

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

Complexity classes

Complexity Classes

An animation that shows the entire problem complexity space

An image that shows the problem space P

Complexity Class -->	P (Polynomial Time)
What it means	Solvable quickly and efficiently
Example	Sorting a list
Analogy	"Filing documents alphabetically"
Key Point	These are "easy" in computational terms

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

An image that shows the problem space P and NP

Complexity Class -->	NP (Non-deterministic Polynomial Time)
What it means	Verifiable solution, hard to find new solution
Example	Verify Soduku puzzle to be correct
Analogy	"Finding a specific document with missing info"
Key Point	Verifying solutions is "easy" but finding new solutions is hard

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

An image that shows the problem space P, NP, and NP-Complete

Complexity Class -->	NP-Complete
What it means	Hardest in NP. Special because solves all NP
Example	Traveling saleman problem
Analogy	"Solving complex jigsaw puzzle, easy to verify, hard to solve"
Key Point	No known efficient solution has been found. but if we do, it will solve all NP

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

An image that shows the problem space P, NP, NP-Complete, and NP-Hard

Complexity Class -->	NP-Hard
What it means	As difficult as NP-Complete or harder
Example	Optimal scheduling with complex dependencies and not verifiable
Analogy	"Scheduling optimal meeting time with many constraints and not verifiable quickly"
Key Point	Maybe impossible to solve practically

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

A digram that asks the age old research question of is P=NP?

Concetti di Informatica