[일반] p-np문제는 사실상 p=np아니냐?

[재민(175.223)]

p-np = p≠np 증명 방법은 np가 풀리지 않지만 푸는 방법은 있는 문젠데 그런것을 완벽히 증명하는건 없었으니까
p-np는 사실상 p=np라 생각된 부분이야 반박 환영할게
욕은 좀 약하게 oFoE29

[ns(qwer2357)]

NP는 NTM이 다항시간안에 푸는 문제들 말하고 P는 TM이 다항시간안에 푸는 문제를 말하는데, TM이 푸는 문제는 NTM으로도 풀 수 있지만 시간이 존나걸려서 TM이 다항시간에 푸는건 NTM이 다항시간안에 못풀수 있다. 는게 대체적인 믿음. P=NP라면 NTM으로 다항시간내 푸는 문제을 TM으로도 다핱시간내 풀수있게 다항시간내 바꿀 수 있어야함

[재민(175.223)]

미안 머가리 깨져서

[이 댓글은 게시물 작성자가 삭제하였습니다.]

이 댓글은 게시물 작성자가 삭제하였습니다.

[ns(qwer2357)]

못하는걸 못한다고 말을 못해서 P != NP가 증명이 안된거고, 못하는걸 못한다고 말을 못한다고 해서 그게 할수있게 되는게 아님. 근데 누가 와서 되는데요? 하고 가면 P=NP가 되고 모두들 닥치게 되겠지만 아직 그 가능성이 남아서 말을 못할뿐 Np는 P가 아닐거라 생각함

[ns(qwer2357)]

NTM 이전에, TM은 알아?

[재민(175.223)]

근데 일단 NTM이 뭐양?

[재민(175.223)]

몰라

[ns(qwer2357)]

TM은 계산기계를 추상화시킨걸로, 무한테이프를 인풋으로 받아서 자기 상태를 바꾸면서 테이프 글자를 바꾸는 기계고, 기계니까 자기한테 프로그램된 알고리즘 따라서 움직이는 애야

[ns(qwer2357)]

NTM은 TM의 확장판으로, 그 기계가 특정 상황에 할 수 있는 일이 여러개가 주어져서, 그 여러가지 가능성중에 한가지로 지 좆대로 움직이는 기계임

[ns(qwer2357)]

그래서 NTM이 어떻게 운좋게 분기를 잘 택해서 다항시간안에 답을 풀 수 있게 하는 알고리즘을 만들면 그렇게 풀리는 문제를 NP라고 부름

[기괴공학도(mecheng98)]

선생님, 죄송한데 " TM이 다항시간에 푸는건 NTM이 다항시간안에 못풀수 있다."고 하셨는데, P subseteq NP 아닌가요? 저는 잘 모르긴 한데요.

[ns(qwer2357)]

미안 거꾸로 말함. ㅇㅇ NTM이 다항시간안에 푸는게 TM이 다항시간안에는 못풀수 있다

[기괴공학도(mecheng98)]

네, 선생님.