np-complete

Fetched 2026-10-26 (cache).

Synonyms: np complete, p-complete, ai-complete

Antonyms: np complete, p-complete, ai-complete

Related words from Datamuse; suggestions, not definitions.

Adjective

1. {{lb|en|computing theory|of a|[[decision problem]]}} That is both [[NP]] (solvable in polynomial time by a non-deterministic Turing machine) and [[NP-hard]] (such that any (other) NP problem can be reduced to it in polynomial time).

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