np-hard
Nghĩa tiếng Việt
Definition & Meaning
English Definition
Describing a problem that is at least as hard as the hardest problems in NP. More formally, a problem H is NP-hard if every problem L in NP can be reduced in polynomial time to H.
Vietnamese Meaning
Mô tả một vấn đề khó ít nhất bằng các vấn đề khó nhất trong lớp NP. Nói một cách chính thức hơn, một vấn đề H là NP-khó nếu mọi vấn đề L trong NP có thể được quy về H trong thời gian đa thức.
Media Context
Interactive Examples (Tap video to Pause/Play).
Examples
-
"The traveling salesman problem is a well-known example of an NP-hard problem."
"Bài toán người bán hàng là một ví dụ nổi tiếng về một vấn đề NP-khó."
-
"Proving a problem is NP-hard is a common way to show that it's unlikely to have an efficient solution."
"Chứng minh một bài toán là NP-khó là một cách phổ biến để chứng minh rằng nó khó có giải pháp hiệu quả."
-
"Many optimization problems are NP-hard."
"Nhiều bài toán tối ưu hóa là NP-khó."
Word Family (Họ từ)
| POS | Word | Meaning |
|---|---|---|
| Noun | NP-hardness | tính NP-khó (độ khó NP) |
Related Words
Subject Area
Etymology (Nguồn gốc)
Usage Note
NP-hard không có nghĩa là vấn đề đó nằm trong NP. Một vấn đề NP-hard có thể nằm ngoài NP, thậm chí không giải được. NP-hard chỉ có nghĩa là nếu tìm ra thuật toán thời gian đa thức để giải một vấn đề NP-hard thì mọi vấn đề trong NP đều có thể giải được trong thời gian đa thức, tức là P = NP.
Collocations (Từ đi kèm)
-
computationally computationally NP-hard (khó theo nghĩa tính toán NP)
-
strongly strongly NP-hard (NP-khó mạnh)
-
problem NP-hard problem (bài toán NP-khó)
-
class NP-hard class (lớp NP-khó)
-
task NP-hard task (nhiệm vụ NP-khó)
-
prove prove NP-hard (chứng minh là NP-khó)
-
show show NP-hard (chỉ ra là NP-khó)
-
reduce reduce to NP-hard (quy về bài toán NP-khó)
Idioms
-
an NP-hard problem
một bài toán NP-khó (ý chỉ một bài toán rất khó tìm ra lời giải hiệu quả trong thời gian đa thức)
"The traveling salesman problem is a classic example of an NP-hard problem."
(Bài toán người bán hàng rong là một ví dụ kinh điển của một bài toán NP-khó.)
-
to prove NP-hard
chứng minh (một bài toán) là NP-khó
"Researchers often try to prove a new computational problem is NP-hard to demonstrate its inherent difficulty."
(Các nhà nghiên cứu thường cố gắng chứng minh một bài toán tính toán mới là NP-khó để thể hiện độ khó vốn có của nó.)
-
NP-hard reduction
phép quy về NP-khó (một kỹ thuật chứng minh một bài toán là NP-khó bằng cách chuyển đổi một bài toán NP-khó đã biết sang nó)
"By showing an NP-hard reduction from a known NP-hard problem, one can establish the NP-hardness of a new problem."
(Bằng cách chỉ ra phép quy về NP-khó từ một bài toán NP-khó đã biết, người ta có thể thiết lập độ khó NP của một bài toán mới.)
Interactive Flashcard
Click the card to flip and test your memory.
np-hard
Tính từMô tả một vấn đề khó ít nhất bằng các vấn đề khó nhất trong lớp NP. Nói một cách chính thức hơn, một vấn đề H là NP-khó nếu mọi vấn đề L trong NP có thể được quy về H trong thời gian đa thức.
"The traveling salesman problem is a well-known example of an NP-hard problem."
Grammar Rules
No specific grammar rules found for this term.
Cultural Context
Khám phá các khía cạnh văn hóa và xã hội thú vị xoay quanh từ "np-hard".