Embedded Files
The World's Full of Problems!
The World's Full of Problems!
Every real-life problem can be formulated into a mathematical problem.
And every mathematical problem can be categorized into a specific complexity-class, based on the Computational Theory.
➕ ➖ ✖ ➗
The Main Complexity Classes:
The Main Complexity Classes:
P
P
Contains problems that have a deterministic polynomial-time algorithm to be solved.
Easy to solve; easy to verify
NP
NP
Contains problems that have a non-deterministic polynomial-time algorithm to be solved.
Hard to solve; easy to verify
NP-Hard
NP-Hard
Contains problems which every other NP problem can be reduced to.
They are at least as hard as the hardest problems in NP.
If there exists a deterministic polynomial-time algorithm for any on of these, all the NP problems could be solved using it.
NP-Complete
NP-Complete
Contains problems that are both NP and NP-Hard.
Are informally called, "the hardest problems" of NP.
Some Examples:
Some Examples:
The SAT Problem
NP-Complete
Jigsaw Puzzle
NP
Linear Search
P
Earthquake Prediction
NP
Addition
P
Sudoku
NP-Complete
Making India 'AATMANIRBHAR'
NP
Super Mario Bros.
NP-Hard
Survey Results
Survey Results
From a small survey of 150 people to know about intuitive difficulty levels:
Jigsaw Puzzle : 77% voters found it to be EASY
Linear Search : 59% voters found it to be EASY
Earthquake Prediction : 82% voters found it to be HARD
Making India 'AATMANIRBHAR' (self-reliant) : 54% voters found it to be HARD
Super Mario Bros. : 51% voters found it to be HARD
Addition of two numbers : 94% voters found it to be EASY
Sudoku : 52% voters found it to be EASY
Prime Factorisation : 75% voters found it to be EASY
Comparison
Comparison
of the intuitive difficulty levels and computational difficulty levels:
Interpretation of Solution:
Interpretation of Solution:
This is not exactly a solution to some real-life problem but the analysis carried out here would surely be utilizable to find one for some other problem. Also, P vs. NP is a classic unsolved problem. It would be wonderful if human intuition towards difficulty levels could be useful for some future research.
Attachments:
Attachments:
Page updated
Google Sites
Report abuse