abbreviation · SCI-REF-007-778Computational Complexity Abbreviations
Abbreviations used to classify computational problems by resource requirements.
Explanation
Abbreviations
| Abbreviation | Full Form | Meaning | Usage Example | Context |
|---|
P | Polynomial Time | The class of decision problems solvable by a deterministic algorithm in polynomial time. | Many standard graph connectivity problems belong to P. | Computational complexity theory. |
NP | Nondeterministic Polynomial Time | The class of decision problems whose proposed solutions can be verified in polynomial time. | SAT is an NP problem. | Complexity classes. |
NP-Hard | Nondeterministic Polynomial-Time Hard | A problem at least as hard as every problem in NP under polynomial-time reductions. | Optimization versions of many difficult problems are NP-hard. | Computational difficulty classification. |
Example or application
A worked example has not yet been added.
Importance
These abbreviations are fundamental for understanding the theoretical limits of efficient computation.
Related Topic
Computational Complexity
Theory of Computation
Algorithms
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Source verification pending; check an authoritative textbook, university, standards body, or peer-reviewed source.
Suggest a correction or source · More in Scientific Abbreviations & Acronyms