Lukas' Notes

NP-complete Problem

May 01, 20261 min read

Definition

NP-complete Problem

A problem is NP-complete if it is in NP and is NP-hard.

Graph View

Backlinks

192.017 Theoretical Computer Science
Many-One Reduction
Maximum Satisfiability Problem
Minimal Vertex Cover Problem
Minimum Vertex Cover Problem
NP-Optimisation Problem
NP-hard Problem
Polynomial Time Reduction
Star Sum Problem
Subset Sum Problem
k-Colouring Problem
k-Satisfiability Problem

Created with Quartz v4.4.0 © 2026

GitHub