[일반] P , NP 질문점여

[익명(211.177)]

P ⊆ NP 라고 했으면서 갑자기

P != NP 는 증명되지 않았지만,

P != NP 를 가정하고 막 NP-complete 따지는건 왜하는거임?

P ⊆ NP 라매

[익명(122.43)]

NP-complete라면 그 문제는 P!=NP인 한 다항시간 내로 못 품

[익명(211.177)]

P ⊆ NP 라는데 P != NP 라면 P !⊆ NP 라는 뜻임? 그니까 둘이 다른집합이라고 가정하고 들어가는 거임?

[익명(223.62)]

np ⊆ p가 증명이 안 됐기 때문인 걸로 아는데

[익명(211.177)]

ㅇㅋ

[익명(223.62)]

np complete의 정의는 np이며, 모든 np문제를 다항 시간 안에 그 문제로 환원할 수 있는 문제임.

[익명(223.62)]

이 정의 자체는 p=np인지 여부에 관계없고.. 근데 보통 np complete면 다항시간에 못푼다고 생각하는거지

[익명(223.62)]

왜냐면 어떤 np complete 문제를 다항시간에 풀었다 라는 건 p=np를 증명했다 라는 것과 동치임. 그니까 좀 더 정확히 말하면 '이건 지금까지 수학자들이 졸루 고민했지만 못 풀었던 문제와 동치구나! 그러면 풀리든, 안 풀리든 어차피 내 낮은 지능을 가지고는 풀 수 없겠네..' 인거임

[익명(211.203)]

P ⊆ NP 이면서 P != NP 인 건 모순이 없는데

[익명(211.177)]

맞네 ㅋㅋ 착각한듯 제가

[익명(211.177)]

아 그러네 ㅋㅋ, P ⊆ NP 인데, P != NP 라면, 어려운 문제가 있다는 뜻이구나

[익명(211.177)]

NP - P 의 원소가 존재한다는 뜻이니깐 ㅇㅋ ㄳ ㄳ