8. NP-complete problems

8.1. Search problems

지수적인 탐색 문제도 있다.

Satisfiability

3-SAT 이상 문제는 NP-난해이다. 2-SAT는 선형 시간에 풀 수 있다.

The traveling salesman problem

여행하는 외판원 문제는 NP-난해이다.

Euler and Rudrata

해밀턴 회로는 NP-난해이다.

Cuts and bisections

그래프 절단 찾기는 NP-난해이다.

Integer linear programming

정수형 선형 계획법은 NP-난해이다.

Three-dimensional matching

3차원 매칭은 NP-난해이다.

Independent set, vertex cover, and clique

독립 집합, 정점 덮개, 클리크는 NP-난해이다.

Longest path

최장 경로 문제는 NP-난해이다.

Knapsack and subset sum

배낭 문제와 부분집합 합 문제는 NP-난해이다.

8.2. NP-complete problems

Hard problems, easy problems:

문제는 NP 문제와 P 문제로 나뉜다.

P and NP

아마도 P ≠ NP일 것이다.

Reductions, again

NP-완전 문제들은 전부 서로 환원될 수 있다.

Factoring

소인부분해는 NP-완전은 아니지만 매우 어렵다.

8.3. The reductions

NP-완전 문제들은 전부 서로 환원될 수 있다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중