NP problem

P 문제(Polynomial problem): 결정론적 튜링머신으로 다항시간 내에 풀수 잇는 문제 
NP 문제 (Non-deterministic Poloynomial problem): 비 결정론적 튜링머신으로 다항시간 내에 풀 수 있는 문제 

다항시간 내에  풀 수 있다는 의미는 시간 복잡도가 O(n^2) , O(n^3) 같이 
튜링 머신(Turing machine)
P-NP 문제를 설명했으니, 이제 튜링머신이 무엇인지 데애서 
결정론적 튜링 머신(Deterministic Turing machine)

비결정론적 튜링 머신(non-deeterministic Turing machine)
NTM 은 튜링 머신에서 특정 상태에서 움직일 수 있는 상태의 개수가 하나로 정해져 있지 않은 경우를 말하낟. 
비결정론적 튜링머신이 주어진 입력이 정답인지 아닌지 계산하는데 다항시간이 걸린다고 하면, 이는 NP문제 라고 하낟. 다시 말하면, 결정론적 튜링머시능로 다항시간에 풀어낼 수 없는 문젣르을 NP문제라고 하낟. 
Co-NP 문제

co-NP문제에 대해서 쉽게 이해하기 위해, 위에서 언급했던 다시 해밀턴 경로를 예를 
No라는 답을 다항시간안에 확인핤 있게 해주느 적당한 모법답안이 존재하지 안혹

Reduction
그 A 문제를 NP-hard 문제 라고 한다. 
환원(reduction)
환원을 가지고 NP-난해 문제를 설명을 했었으니, 이제 

덧셈 문제는 곱셈 문제보다느 ㄴ어렵다라고 정의하는 것이고, 덧셈문제를 해결할 수 잇다면 곱셈 문제도 당연히 해결할 수 잇다.(곱셈
NP-난해 문제는 이세상에 있는 모든 NP무넺보다 어렵다라고 정의할 수 있는 것이다. 


정지문제 
정지 문제는 간단하게 설명하면, 문제는 명확하게 제시되어 잇지만, 풀 수 없는 무넺라고 증명된 문제이다. 
나무 위키에서 너무나도 쉽게 정의해 놓았다. 
좀 더 부가적인 설명을 하자면,exit 라는 프로그램에 

NP 완전 (NP-complete)문제
NP 난해 문제에도 포함되며, 

NP 난해 문제에도 포함되며, NP문제에도 포함된다면 이를 완전 NP-complete 문제라고 한다. NP 문제들 중에 풀 수 잇느 ㄴ가장 어려운 문제라고
NP 난해 문제는 모든 NP 문제보다 어려운문제라고. 했으며

NP-완전 문제중 단 하나로 다항 시간내에에 풀어낼 수 이싿며 ㄴ

NP-완전 문제 중 단 하나라도 다항 시간 내에 풀어낼 수 잇다면, 환원에 의해 모든 NP를 다항시간에 풀어 낼 수 있으므로 (왜냐하면 모든 NP문제는 NP-complete문제보다는 쉬우니가) p=np 인 것ㅇ르 증명할 수 있다. 
좀 더 부가 설명을 하자면, nP문제에 속하는 Np-hard문제 와 nP 문제에 속하지 않는 np-hard 문제의 차이은 결정가능한 지으이 여부이다. 

다이어 그램이 두개인 이유는, 아직 P=NP 인지, P!=NP인지 증명이 안되어 있기 때문이디ㅏ. 
이제까지 설명한 것을 바탕으로, 위의 다이어그을 보며 난이도 순으로 다시 한번 설명해보자. 
P문제는 정렬 문제와 같이 결정론적 튜링 머신으로 쉽게 풀어낼 수 있느 ㄴ문들을 말하낟 NP문제는 비 결정론적 튜링 머신으로 다항시간 내에 풀어낼 수 잇느 ㄴ즉, 시간이 오래 걸리는 문제들을 말하낟. 그리고 모든 NP 문제들을 어떤 문제로 A로 환원할 수 잇고 환원한 문제를 해결할 수 잇다면 이 문제 A는 정확히 말하면NP -난해 문제이자 NP-완전문제, 환원한 문제를 해결할 수 없다면 이를 nP-난해(ㅞ


모든 NP 문제들을 이 어떤 문제 A로 환원할수 잇고 환원한 문제를 해결할 수 잇다면, 이 문제 A는 NP-완전 문제이라하고 (정확히 말하면 NP-난해 문제이자 NP-완전문제) 환원한 문제를 해결할 수없다면 이를 NP-난해 (NP-hard)라고 한다.
P-NP 문제는 복잡도 종류 P와 NP가 같은지에 대한 컴ㅍ

어떤 NP 완전 문제가 2차 혹은 선형 시간 안에 풀릴 수 잇는지 아닌지를 물었다. P

P-NP 문제는 복잡도 종류 P와 

P는 결정론적 튜링 기계를 사용해 다항 시간내에 답을 구할 수 있는 문제의 집합
NP는 비 결정론적 튜링 기계를 사용해 다항시간내에 답을 구할 수 있는 문제의 집합이다. 

여기에서 결정론적 튜링기계에 사용한 프로그램을 비결정론적 튜링 기계에 적용할 수 있으므로, P는  NP의 부분집합이 된다.  하지만 여기에서 P와 NP가 같은 집합인지, 아니면 P 가 NP의 진부분집합인지는 아직 밝혀지지 않았다. 


P=NP 라고 하면 시간 복잡도 (2n_n-1)회 안에 풀리는 이 문제를 다항시간에 풀 수 있는 알고리즘이 존재할 것이다. 이런 이유로 이 문제는 빠르게 확인가능한 NP 안에 있지만 반드시 빠르게 풀 수 있는 P안에 있지는 않다. 

P=NP문제의 답은, 부분집합의 합계문제와 같이 지수시간 안에 답을 계산할 수 있는 문제들이 다항시간안에도 답을 계산할 수 있는지를 결정할 것이다.
 만약 P=/ NP 인것으로 드러난다면, NP 안에는 풀이법을 확인하는 것보다 답을 계산하는게 더 어려운 문제들이 잇다는 것을 의미할 것이다. 그것들은 다항시간 안에 풀 수 없지만 다항시간안에 풀이법을 찾을 수는 있다.

NP-Hard(NP-난해)
어떤 문제가 주어졌을때, 다른 NP문제의 입력을 그 문제의 입력으로 변환할 수 있는 변환할 수 있는 환산 알고리즘이 존재하고 이 환산 알고리즘은 수행시간이 무시 될 수 있을 정도로 빠르다면 이 문제는 NP-난해 문제에 속한다. 이 집합이 중요한 이유는 NP-난해에 속하는 문제 중 하나라도 P에 속한다는 것을 밝힌다면 P=NP 를 증명할 수 있기 때문이다. 

NP-완전
NP난해 문제이면서 NP문제인 문제는 NP-완전문제에 속한다.


다항시간안에 답을 제공할 수 있는 알고리즘이 있는 문제들의 종합적인 모임을 P류 혹은 P라고 한다. 

여기서 결정론적 튜링 기계는 ~를 의미하고. 
비결정론적 튜링 기계는 ~를 의미한다. 
진부분집합은 ~를 의미한다. 
빠르게는 다항시간안에 실행되는 작업을 위한 알고리즘의 존재를 의미


3-상태 아주 빠쁜 기계의 튜링 기계를 유한 오토마타에 입각해 표현해 본것 각각은 원은 표의 상태를 나타내고, m배열, 지시, 또는 명령은 화살표로 표현된다. 화살표 위의 표식은 특정한 변화를 야기하는 읽히는 기호를 결정하고 슬래쉬 뒤의 동작은 띠라오는 행동을 의미한다.

범용 튜링 기계
- 튜링은 미결정성에 다음과 같이 적었다. (계산 가능한 수열을 계산하는 단일 기계를 만들 수 있다. 만약 이 기계에 U에 들어온 테이프의 처음 부분이 어떤 계산기ㅖ M이 처리한 세미콜론으로 분할된다.
- 실제 컴퓨터가 연산할 수있다면 튜링 기게 역시 

튜링 기계의 한계 (시간 복잡도 이론)
튜링 기계의한계는 일부 배열들의 능력을 잘 모델링하지 못한다. 랜덤 접근 저장 프로그램 기계(Random Access Store Program Machine)들의 실질적인 예이다. 
범용 튜링 기계와 같이 RASP는 무한걔의 구분 가능한, 동시에 셀 수 있지만 무한한 레지스터를 가지고 잇다. RASP의 유한 상태는 레지스터 배열에 있는 다른 레지스터를 호출하는 것이 가능하다. 메모리 인덱스를 이용한 연산의 최적화가 튜링 기계에서는 불가능하므로 튜