Lukas' Notes

Search titles, aliases and note text. Use # for tags.

NP-complete Problem

1 min read

Definition

NP-complete Problem

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

Backlinks

192.017 Theoretical Computer Science
Exercise Sheet 1
Exercise Sheet 3
Lecture 3
Some NP-Complete Problems Fit Through Subexponential Gaps
Subexponential Time Needs a Ruler
3-Satisfiability Decision Problem
4-Colouring Problem
Chamberlin-Courant Approval Voting Rule (COMSOC)
Dichotomy Theorem (Constraint Satisfaction)
Distinct Row Matrix Completion Decision Problem
Kemeny Score Problem (COMSOC)
Many-one Reduction
Maximum Satisfiability Problem
Minimal Vertex Cover Problem
Minimum Vertex Cover Problem
NP-hard Problem
NP-intermediate Problem
Polynomial Time Reduction
Proportional Approval Voting Rule (COMSOC)
Star Sum Problem
k-Colouring Problem
k-Satisfiability Problem

Created with Quartz v4.5.2 © 2026

GitHub