---
tag: ZD214Q58SB
kind: concept
name: Non-deterministic polynomial time
sources:
  - wikipedia: en:76765067@r1368301704
    locator: Glossary of logic, section N
    note: adopted
    mention: wikipedia://en/76765067#Y5Q0
    sections: [Summary]
inventory: [5DF3PXQARM]
---

## Summary

The complexity class NP, consisting of decision problems for which a 'yes' answer can be verified by a deterministic Turing machine in polynomial time, given the correct certificate or witness.