Algorithms - P, NP, NP-Complete, NP-Hard
date
Jan 11, 2025
type
Post
AI summary
slug
algorithm-p-np
status
Published
tags
Algorithm
summary
Table of Key Differences:
Category | Definition | Examples | Relation to Others |
P | Problems solvable in polynomial time by a deterministic Turing machine. | Sorting, Searching | |
NP | Problems verifiable in polynomial time by a deterministic Turing machine. | Sudoku, SAT | , but not all NP problems are P. |
NP-Complete | Problems that are both in NP and as hard as any problem in NP (if one can be solved in P, all can). | SAT, 3-SAT | Subset of NP; . |
NP-Hard | Problems at least as hard as NP-Complete problems but may not be in NP (not verifiable in poly time). | TSP (optimization) | Contains NP-Complete; |
TO-DO:
- reduction to NP-Complete problems
- list of typical NP-Complete problems