Last Updated ：2025/11/23

NP-complete

not-comparable of a decision problem

(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).

Japanese Meaning

NP完全問題：計算理論において、ある決定問題が、非決定性チューリング機械で多項式時間内に解けるNP問題であり、かつ全てのNP問題が多項式時間内に還元可能なNP困難な問題であることを示す。

What is this buttons?

Determining whether a given graph has a Hamiltonian cycle is an NP-complete problem that remains intractable for large instances.

Google Translation / DeepL Translation

与えられたグラフがハミルトン閉路を持つかどうかを判定する問題は、NP完全（非決定性多項式時間に属し、かつNP困難である）であり、大規模なインスタンスでは手に負えないままである。

Details

Sense（1）

Informally, a problem is in the class NPC—and we refer to it as being NP-complete—if it is in NP and is as "hard" as any problem in NP. We shall formally define what it means to be as hard as any problem in NP later in this chapter. In the meantime, we will state without proof that if any NP-complete problem can be solved in polynomial time, then every problem in NP has a polynomial-time algorithm. Most theoretical computer scientists believe that the NP-complete problems are intractable, since given the wide range of NP-complete problems that have been studied to date—without anyone having discovered a polynomial-time solution to any of them—it would be truly astounding if all of them could be solved in polynomial time. Yet, given the effort devoted thus far to proving NP-complete problems intractable—without a conclusive outcome—we cannot rule out the possibility that the NP-complete problems are in fact solvable in polynomial time.

Google Translation / DeepL Translation