복잡도 P, NP

1 개요

P, 복잡도 P, P 문제

• 복잡도 종류의 하나
• 정해진 단계 안에 풀리는 문제
• 특정한 횟수 안에 정확하게 답할 수 있는 문제의 집합
• 결정론적 튜링 기계로 다항 시간 안에 풀 수 있는 판정 문제 ★
• 예: 선형 계획 문제, 최대공약수 문제, 주어진 숫자가 소수인지 판별하는 문제

2 같이 보기

• NP

3 참고 자료

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