P-complete

adjective

Describing any problem in the complexity class P to which there exists a polynomial time mapping from any other problem in P.

Ask AI about this wordChatGPTClaudePerplexityGoogle AIGrok

Meanings

adjectiveP-complete (not comparable)
  1. not comparablecomputingDescribing any problem in the complexity class P to which there exists a polynomial time mapping from any other problem in P.
proper noun
  1. computingThe set of such problems.

Translations

Finnish P-täydellinen
  • P-täydellinendescribing any problem in P to which there exists a polynomial time mapping from any other problem in P
German P-vollständig
  • P-vollständigdescribing any problem in P to which there exists a polynomial time mapping from any other problem in P
Cite this entry
APA

P-complete. (n.d.). In WatkinsX Dictionary. Retrieved November 2, 2026, from https://dictionary.watkinsx.com/word/P-complete

MLA

“P-complete.” WatkinsX Dictionary, https://dictionary.watkinsx.com/word/P-complete. Accessed November 2, 2026.

Chicago

WatkinsX Dictionary, s.v. “P-complete,” accessed November 2, 2026, https://dictionary.watkinsx.com/word/P-complete.

Source: P-complete on Wiktionary, CC BY-SA 4.0.