from lecture
결정론적 튜링 기계
p: 결정론적 튜링 기계로 다항식 시간 안에 풀 수 있는 문제
np: 비결정론적 튜링 기계로 풀 수 있는 문제 중 > 정답이 있을 때 결정론적 튜링 기계로 다항식 시간 안에 검증 가능한 문제
np-complete: intersection of np ∩ np-hard.
np-hard: np가 아닌데 np가 붙어 있다 =_=
| p ⊂ np
| np-complete = np ∩ np-hard
| np-complete ⊂ np
from ChatGPT
P, NP 및 NP-완전 다이어그램은 계산 복잡도 이론에서 결정 문제의 복잡도 클래스를 나타냅니다. 각 클래스와 그 관계에 대한 간략한 설명은 다음과 같습니다.
P: 클래스 P는 결정론적 알고리즘에 의해 다항 시간 내에 풀 수 있는 결정 문제를 포함합니다. 이것은 알고리즘의 실행 시간이 입력 크기의 일부 다항식 함수에 비례한다는 것을 의미합니다. P의 문제는 "효율적으로 해결할 수 있는" 것으로 간주됩니다.
NP: 클래스 NP는 비결정론적 알고리즘에 의해 다항 시간에 검증될 수 있는 결정 문제를 포함합니다. 이는 답이 정확하다는 "인증서"가 주어지면 다항 시간 내에 검증을 수행할 수 있음을 의미합니다. NP 문제는 "효율적으로 검증 가능한" 것으로 간주됩니다.
NP-완전: 문제가 NP에 있고 NP의 모든 문제가 다항식 시간으로 축소될 수 있으면 NP-완전입니다. 이는 NP-완전 문제에 대해 효율적인 알고리즘을 찾으면 NP의 모든 문제를 해결하는 데 사용할 수 있음을 의미합니다. NP-완전 문제는 NP에서 "가장 어려운" 문제로 간주됩니다.
다음은 이러한 클래스 간의 관계를 나타내는 다이어그램입니다.
+----------+
| NP |
+----------+
|
|
+--------|--------+
| | |
+----+---+ +--+--+ +--+--+
| P | NPC | NP |
+---------+ +------+보시다시피 P는 NP의 하위 집합이며 NP-완전 문제는 NP와 NP-하드 문제의 교차점입니다. NP-hard 문제는 적어도 NP-complete 문제만큼 어려운 결정 문제이지만 반드시 NP에 속하지는 않습니다.
In the context of computational complexity theory, the terms P, NP, NP-complete, and hard (referring to NP-hard) are used to classify problems based on their difficulty and the time it takes to solve them.
P (Polynomial Time): P represents the class of decision problems (problems with a yes/no answer) that can be solved in polynomial time by a deterministic Turing machine. In other words, problems in P can be solved relatively quickly by a deterministic algorithm whose running time is a polynomial function of the input size.
NP (Nondeterministic Polynomial Time): NP is the class of decision problems that can be solved in polynomial time by a nondeterministic Turing machine. This means that if the answer to a problem is 'yes,' there exists a solution that can be verified in polynomial time. Problems in NP are not necessarily easy to solve, but their solutions can be checked quickly once found.
NP-complete: A problem is NP-complete if it is in NP, and every other problem in NP can be reduced to it using a polynomial-time transformation. This means that if a fast (polynomial time) algorithm could be found for any NP-complete problem, then fast algorithms could be found for all problems in NP. The first problem proven to be NP-complete was the Satisfiability problem (SAT), and many other problems have been proven NP-complete since then.
NP-hard: A problem is considered NP-hard if it is at least as hard as the hardest problems in NP. This means that every problem in NP can be reduced to the NP-hard problem in polynomial time. NP-hard problems are not necessarily in NP, and some of them may not even have a yes/no answer (unlike decision problems). If an NP-hard problem is also in NP, then it is NP-complete.
In summary, P problems are considered "easy" to solve, whereas NP problems have solutions that are "easy" to verify once found. NP-complete problems are the hardest problems within NP, and if an efficient solution is found for any NP-complete problem, all NP problems become solvable in polynomial time. NP-hard problems are at least as hard as the hardest problems in NP and may be even harder.
댓글