| 7번째 줄: | 7번째 줄: | ||
* [[복잡도 종류]]의 하나 | * [[복잡도 종류]]의 하나 | ||
* 정해진 단계 안에 풀리는 문제 | * 정해진 단계 안에 풀리는 문제 | ||
* 다항식 시간 내에 풀 수 있는 문제들 | |||
* 특정한 횟수 안에 정확하게 답할 수 있는 문제의 집합 | * 특정한 횟수 안에 정확하게 답할 수 있는 문제의 집합 | ||
* 결정론적 튜링 기계로 다항 시간 안에 풀 수 있는 판정 문제 ★ | * 결정론적 튜링 기계로 다항 시간 안에 풀 수 있는 판정 문제 ★ | ||
| 14번째 줄: | 15번째 줄: | ||
==복잡도 NP== | ==복잡도 NP== | ||
* 대략 어려운 문제 | * 대략 어려운 문제 | ||
* 다항식 시간 내에 해법을 검산할 수 있는 문제들 | |||
* 비결정론적 튜링 기계(NTM)로 다항 시간 안에 풀 수 있는 판정 문제의 집합 | * 비결정론적 튜링 기계(NTM)로 다항 시간 안에 풀 수 있는 판정 문제의 집합 | ||
2016년 8월 23일 (화) 23:34 판
- P, P 문제, 복잡도 P
- NP, NP 문제, 복잡도 NP
1 복잡도 P
- 대략 쉬운 문제
- 복잡도 종류의 하나
- 정해진 단계 안에 풀리는 문제
- 다항식 시간 내에 풀 수 있는 문제들
- 특정한 횟수 안에 정확하게 답할 수 있는 문제의 집합
- 결정론적 튜링 기계로 다항 시간 안에 풀 수 있는 판정 문제 ★
- 주어진 문제를 푸는 알고리즘이 걸리는 시간이 어떤 다항식으로 나타날 때
- 예: 선형 계획 문제, 최대공약수 문제, 주어진 숫자가 소수인지 판별하는 문제
2 복잡도 NP
- 대략 어려운 문제
- 다항식 시간 내에 해법을 검산할 수 있는 문제들
- 비결정론적 튜링 기계(NTM)로 다항 시간 안에 풀 수 있는 판정 문제의 집합
3 같이 보기
4 참고 자료
5 같이 보기
6 참고 자료
로그인하시면 댓글을 쓸 수 있습니다.
{{ comment.name }}
{{ comment.created | snstime }}
-
{{comment.page_title}} ―{{comment.name}}