Don't make it complicated. 🤗

봉봉·2022년 7월 26일

CS

목록 보기

2/7

'NP' 문제

'비결정적 다항 Nonedeterministic Polynomial' / '다항 Polynomial', 'P'

다항 시간 안에 풀 수 있는 판정 문제의 집합으로, 비결정론적 다항시간(Non-deterministic Polynomial time)

문제에 따른 맞는 답인지 모르고 답의 후보군에 속한 확실하지 않은 답이 주어졌을 때,
올바른 답인지 판단 가능케 해주는 '(polynomial) Time Complexity 시간 복잡도' 알고리즘이 존재하는 그 문제들을 'NP'라 분류.

'쉬운' 문제는 복잡도 면에서 '다항'.

지수가 2보다 크면 적용하기 어려울 수 있는 부류의 문제 'P'.
이를 N² 같은 어떤 다항식으로 표현되는 실행 시간, 즉 다항 시간내에 해결할 수 있기 때문.

'NP' 문제라는 집합으로부터 파생된 2개의 추가적인 문제 집합 'NP-Complete'와 'NP-Hard'

자기 자신으로 다항식 시간내에 환원될 수 있는 모든 'NP' 문제들의 분류.

'NP-Hard' 문제들 중, 'NP' 문제이기도 한 문제들.
일반적으로 'NP-Hard' 문제는 'NP' 문제가 아닐 수 있는데,
그 중 'NP' 문제이기도 한 문제들을 따로 'NP-Complete' 라 분류.

복잡도를 다룰 때

"어떤 문제는 답을 계산하는 데 극한의 시간이 필요하겠지만 모든 문제를 난해하게 접근할 필요는 없다."

"복잡도의 결과는 N이 큰 값일 때만 적용되는 점근적(asymptotic) 척도"

예)
f(n) = n² + 3n이면 n이 매우 커질수록 항 3n은 n²에 비해 무의미해지며, 함수 f(n)은 n이 무한대에 가까워짐에 따라 n²과 점근적으로 동일.

현실에서는 이러한 점근적 작동 방식이 문제가 되지 않을 정도로 작을 수도 있는 N,
그래서 실제 상황에서는 대부분 근사치만 구하는 것으로도 충분.

"완전히 최적인 해법을 구할 필요는 없다."