복잡도 P, NP

P, P 문제, 복잡도 P, 다항시간문제

NP, NP 문제, 복잡도 NP, 미정다항시간문제

1 복잡도 P

• 대략 쉬운 문제
• 복잡도 종류의 하나
• 정해진 단계 안에 풀리는 문제
• 다항식 시간 내에 풀 수 있는 문제들
• 특정한 횟수 안에 정확하게 답할 수 있는 문제의 집합
• 결정론적 튜링 기계로 다항 시간 안에 풀 수 있는 판정 문제 ★
• 주어진 문제를 푸는 알고리즘이 걸리는 시간이 어떤 다항식으로 나타날 때
• 예: 선형 계획 문제, 최대공약수 문제, 주어진 숫자가 소수인지 판별하는 문제

2 복잡도 NP

• 대략 어려운 문제
• 다항식 시간 내에 해법을 검산할 수 있는 문제들
• 비결정론적 튜링 기계(NTM)로 다항 시간 안에 풀 수 있는 판정 문제의 집합

3 같이 보기

• NP-난해
• NP-완전
• P-NP 문제
• 복잡도 종류

4 참고 자료

• https://ko.wikipedia.org/wiki/NP_(복잡도)

5 같이 보기

• NP

6 참고 자료

• https://ko.wikipedia.org/wiki/P_(복잡도)