✦ScienexySCIENCE KNOWLEDGE LIBRARY
abbreviation · SCI-REF-007-778

Computational Complexity Abbreviations

Abbreviations used to classify computational problems by resource requirements.

Explanation

Abbreviations

AbbreviationFull FormMeaningUsage ExampleContext

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