NP-hard

국민대학교에서 "쉽게 배우는 알고리즘" 교재를 이용한 박하명 교수님의 강의 교안을 이용하여 수업 내용을 정리하였습니다  NP-Completeness 개요  P : 다항시간에 풀 수 있는 결정 문제 집합 NP : 비결정론적으로 다항시간에 풀 수 있는 결정 문제 집합 => 답을 다항시간에 검증할 수 있는 문제(다항시간에 검증할 수 있으면 NP 문제) NP-Hard : 모든 NP 문제에서 다항시간 변환되는 문제 집합 => 검증이 안될 수 도 있음 (NP - Complete와의 차이) NP-Complete : NP-Hard 이면서 NP인 문제(결국 NP이기에 yes/no의 결정문제 집합임) NP-Hard 증명 방법 문제 A가 NP-Hard 임을 증명하는 방법에는 2가지가 있음 1. NP-Hard 정의에 따라 모..

국민대학교에서 "쉽게 배우는 알고리즘" 교재를 이용한 박하명 교수님의 강의 교안을 이용하여 수업 내용을 정리하였습니다  Motivation 외판원 순환 문제 (TSP : Travelling salesman problem)    모든 정점을 방문하고 시작 정점으로 돌아오는 최단 경로를 찾는 문제인데 Brute-force 방식으로 n개의 정점의 모든 permutation(순열)을 조사해야함 => O(n!) TSP 문제를 다항시간에 푸는 알고리즘이 존재할까? 이론상 불가능함 Types of Problems   Tractable Problem : 입력 n에 대하여 푸는데 걸리는 시간이 다항 함수 f(n) 으로 표현 되는 문제 Intractable Problem: 다항 시간안에 풀 수 없는 문제=> Θ(2^n) ..