[일반] NP complete 증명할 때 왜 'reduce'라고 표현하나요?

[익명(147.46)]

A : NP-complete를 알고 있을 때 B가 complete한가? 에 대하여

B ∈ NP임을 보이고, A의 instance를 B로 polytime에 reduce할 수 있으면 B는 NP-complete (A ≤ pB)

까지는 좋아요

근데 pB 에서 p가 뭘 의미하는 건지,

그리고 A reduce to B에서 reduce가

왜 reduce라고 하는건지 잘 모르겠어요

[익명(110.12)]

p가 B에붙는게 아니고 부등호에 붙는걸껄? Polynomial reduction이라는거 표시하려고 쓰는거임

[익명(147.46)]

아 감사합니다!

[익명(223.39)]

문제 A를 시간복잡도를 더 키우지 않고 문제 B로 바꾼다는 뜻일걸

[익명(147.46)]

더 키우지 않는다라고 하면 말 되긴 하네요

[익명(223.39)]

1)문제 A의nput을 문제 B껄로 바꾸고, 2)B 풀고, 3)B output을 A의 output으로 바꾸고 에서 1,3단계 다항시간안에 하면

[익명(223.39)]

NP에선 시간복잡도 차이가 없으니까 만약 A,B다 NP이면

[daWn(jini8057)]

환원된다는 뜻 아님?

[익명(147.46)]

걍 문제를 바꾼다는 건 알긴 한데 왜 reduce일까 싶어서요

[daWn(jini8057)]

환원이 근원으로 돌아간다는 뜻이잖아. 문제가 겉모습은 달라보여도 기저에 있는 원리를 들여다 보면 비슷한 문제가 되는 걸 표현한 게 아닐까 싶음

[익명(112.151)]

어떤 교수는 환원이나 reduce라는 말 싫어하고 바꿔풀기라고하더라 사실 바꿔풀기가 직관적이긴한듯

[익명(112.151)]

근데 문제를 바꿔풀때 더 쉬운문제로 바꿔야 말이되잖아? 그런의미에서 reduce라고하는듯. (하지만 사실상 바꾼다고 문제는 쉬워지지않는경우가많고 특히 어떤 np완전문제를 다른문제로 바꾸는경우 그러함)

[익명(147.46)]

A에 속하는 instance하나를 B로 바꾼 건데 그러면 B가 A를 포함해서 더 general한 문제로 바뀌는 거 아닌가요? 더 general한 게 더 쉬운 건 아닌 거 같을 거 같긴 한데... 물론 쓰신 거 처럼 더 쉬운(?)게 아니긴 한데 애초에..

[익명(112.151)]

예를들면 어떤사람의 문제는 자존감이 낮은건데 이 문제를 그 사람이 못생겼다는 문제로 reduce할수있고 (잘생기면 인기많아지고 자존감높아짐) 또 그 문제를 돈이없다는 문제로 reduce 할수있음 (돈많으면 피부관리와 성형수술 명품으로 잘생겨지는거가능) 좀 더 원래 문제를 좀 더 쉬운(쉬워보이는) 문제로 reduce 하는거지

[익명(112.151)]

근데 reduce 라는말이 애매하긴한게 돈문제가 자존감문제볻 쉬운문제냐? 라고물으면 yes라고 답하긴 또 어렵지

[ns(qwer2357)]

너가 x^3 sin (1/x^2)을 미분하라. 라는 문제를 받았을때 이걸 곱의미분법과 합성함수의 미분법을 써서 x^3을 미분할 수 있다. sin(x)를 미분할 수 있다. 1/x^2을 미분할 수 있다. 로 줄이잖아. (사칙연산이나 합성 빼면) 즉 뒤에거 하면 앞에건 할 수 있게되면 앞의 문제를 뒤의 문제로 문제를 줄인거지.