Lukas' Notes

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

Nondeterministic Polynomial Complexity Class

1 min read

Definition

Nondeterministic Polynomial Complexity Class

The complexity class is the set of all decision problems for which there exists a polynomial balanced and polynomial decidable certificate relation for .

Backlinks

192.017 Theoretical Computer Science
192.026 Efficient Algorithms
Certificate (Complexity Theory)
Chamberlin-Courant Winner Determination Decision Problem
Independent Set to Chamberlin-Courant Winner Determination (Karp Reduction)
Independent Set to Proportional Winner Determination (Karp Reduction)
Minimax Approval Voting Rule (COMSOC)
NP-complete Decision Problem
NP-hard Decision Problem
Nondeterministic Polynomial Problem
P equals NP
P not equals NP
P vs NP Problem
Proportional Winner Determination Decision Problem

GitHub