What does p-complete mean?

Definitions for p-complete

Here are all the possible meanings and translations of the word p-complete.


  1. 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.

  2. P-complete(ProperNoun)

    The set of such problems.


  1. P-complete

    In complexity theory, the notion of P-complete decision problems is useful in the analysis of both: ⁕which problems are difficult to parallelize effectively, and; ⁕which problems are difficult to solve in limited space. Formally, a decision problem is P-complete if it is in P and that every problem in P can be reduced to it by using an appropriate reduction. The specific type of reduction used varies and may affect the exact set of problems. If we use NC reductions, that is, reductions which can operate in polylogarithmic time on a parallel computer with a polynomial number of processors, then all P-complete problems lie outside NC and so cannot be effectively parallelized, under the unproven assumption that NC ≠ P. If we use the weaker log-space reduction, this remains true, but additionally we learn that all P-complete problems lie outside L under the weaker unproven assumption that L ≠ P. In this latter case the set P-complete may be smaller.


  1. Chaldean Numerology

    The numerical value of p-complete in Chaldean Numerology is: 2

  2. Pythagorean Numerology

    The numerical value of p-complete in Pythagorean Numerology is: 6

Examples of p-complete in a Sentence

  1. Marge Ahrens:

  2. The Anderson:

  3. Dean Monco:

  4. Fox News:

  5. Read MoreThe source:

Images & Illustrations of p-complete

  1. p-completep-completep-complete


Find a translation for the p-complete definition in other languages:

Select another language:

  • - Select -
  • Chinese - Simplified 简体中文 (Chinese - Simplified)
  • Chinese - Traditional 繁體中文 (Chinese - Traditional)
  • Spanish Español (Spanish)
  • Japanese 日本語 (Japanese)
  • Portuguese Português (Portuguese)
  • German Deutsch (German)
  • Arabic العربية (Arabic)
  • French Français (French)
  • Russian Русский (Russian)
  • Kannada ಕನ್ನಡ (Kannada)
  • Korean 한국어 (Korean)
  • Hebrew עברית (Hebrew)
  • Ukrainian Український (Ukrainian)
  • Urdu اردو (Urdu)
  • Hungarian Magyar (Hungarian)
  • Hindi मानक हिन्दी (Hindi)
  • Indonesian Indonesia (Indonesian)
  • Italian Italiano (Italian)
  • Tamil தமிழ் (Tamil)
  • Turkish Türkçe (Turkish)
  • Telugu తెలుగు (Telugu)
  • Thai ภาษาไทย (Thai)
  • Vietnamese Tiếng Việt (Vietnamese)
  • Czech Čeština (Czech)
  • Polish Polski (Polish)
  • Indonesian Bahasa Indonesia (Indonesian)
  • Romanian Românește (Romanian)
  • Dutch Nederlands (Dutch)
  • Greek Ελληνικά (Greek)
  • Latin Latinum (Latin)
  • Swedish Svenska (Swedish)
  • Danish Dansk (Danish)
  • Finnish Suomi (Finnish)
  • Persian فارسی (Persian)
  • Yiddish ייִדיש (Yiddish)
  • Armenian հայերեն (Armenian)
  • Norwegian Norsk (Norwegian)
  • English English (English)

Discuss these p-complete definitions with the community:

Word of the Day

Would you like us to send you a FREE new word definition delivered to your inbox daily?

Please enter your email address:


Use the citation below to add this definition to your bibliography:


"p-complete." Definitions.net. STANDS4 LLC, 2019. Web. 22 Feb. 2019. <https://www.definitions.net/definition/p-complete>.

Are we missing a good definition for p-complete? Don't keep it to yourself...

Free, no signup required:

Add to Chrome

Get instant definitions for any word that hits you anywhere on the web!

Free, no signup required:

Add to Firefox

Get instant definitions for any word that hits you anywhere on the web!

Nearby & related entries:

Alternative searches for p-complete:

Thanks for your vote! We truly appreciate your support.