p-complete

Fetched 2026-10-26 (cache).

Synonyms: np-complete, complete, incomplete, uncomplete, np complete, ai-complete, recomplete

Antonyms: np-complete, complete, incomplete, uncomplete, np complete, ai-complete, recomplete

Related words from Datamuse; suggestions, not definitions.

Adjective

1. {{lb|en|computing theory}} Describing any problem in the complexity class [[P]] to which there exists a [[polynomial time]] mapping from any other problem in [[P]].

Proper noun

1. {{lb|en|computing theory}} The [[set]] of such problems.

Source: Wiktionary · CC BY-SA 4.0 (Wiktionary dump) · cached copy, not a rewrite.