(→개요) |
Jmnote bot (토론 | 기여) 잔글 (봇: 자동으로 텍스트 교체 (-==참고 자료== +==참고==)) |
||
| (다른 사용자 한 명의 중간 판 6개는 보이지 않습니다) | |||
| 1번째 줄: | 1번째 줄: | ||
== | ;P, P 문제, 복잡도 P, 다항시간문제 | ||
;NP, NP 문제, 복잡도 NP, 미정다항시간문제 | |||
==복잡도 P== | |||
* 대략 쉬운 문제 | |||
* [[복잡도 종류]]의 하나 | * [[복잡도 종류]]의 하나 | ||
* 정해진 단계 안에 풀리는 문제 | * 정해진 단계 안에 풀리는 문제 | ||
* 다항식 시간 내에 풀 수 있는 문제들 | |||
* 특정한 횟수 안에 정확하게 답할 수 있는 문제의 집합 | * 특정한 횟수 안에 정확하게 답할 수 있는 문제의 집합 | ||
* 결정론적 튜링 기계로 다항 시간 안에 풀 수 있는 판정 문제 | * 결정론적 튜링 기계로 다항 시간 안에 풀 수 있는 판정 문제 ★ | ||
* 주어진 문제를 푸는 알고리즘이 걸리는 시간이 어떤 다항식으로 나타날 때 | |||
* 예: 선형 계획 문제, 최대공약수 문제, 주어진 숫자가 소수인지 판별하는 문제 | * 예: 선형 계획 문제, 최대공약수 문제, 주어진 숫자가 소수인지 판별하는 문제 | ||
==복잡도 NP== | |||
* 대략 어려운 문제 | |||
* 다항식 시간 내에 해법을 검산할 수 있는 문제들 | |||
* 비결정론적 튜링 기계(NTM)로 다항 시간 안에 풀 수 있는 판정 문제의 집합 | |||
==같이 보기== | |||
*[[NP-난해]] | |||
*[[NP-완전]] | |||
*[[P-NP 문제]] | |||
*[[복잡도 종류]] | |||
==참고== | |||
* https://ko.wikipedia.org/wiki/NP_(복잡도) | |||
[[분류: 복잡도]] | |||
==같이 보기== | ==같이 보기== | ||
*[[NP]] | *[[NP]] | ||
==참고 | ==참고== | ||
* https://ko.wikipedia.org/wiki/P_(복잡도) | * https://ko.wikipedia.org/wiki/P_(복잡도) | ||
[[분류: 복잡도]] | [[분류: 복잡도]] | ||
2017년 7월 15일 (토) 03:29 기준 최신판
- 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}}