NPC1 p, np, np-complete, np-hard + polynomial time(n^k: n is the size of input, k is constant) 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는 결정론적 알고리즘에 의해 다항 시간 내에 .. 2023. 3. 25. 이전 1 다음