sat을 다항시간 안에 못 풀고 (sat을 다항시간안에 푸는 알고리즘이 증명 안된 상태) 풀이는 답은 다항시간안에 맞는지 체크 가능한 문제 |
[일반] np 완비 문제의 정의가 이거 맞나요?
익명(110.11)
2018-09-04 14:09
추천 0
댓글 6
다른 게시글
-
님들 책 읽을 때 속발음 하면서 읽음?? [2][일반] dd(110.11) | 18.09.04추천 0
-
(호에에 하와와) dfs bfs가 넘 어려워요 후에엥 [5][일반] 치카냥(miku133) | 18.09.04추천 0
-
문제풀때 C++쓰시는분들 배열쓰세요 아니면 벡터쓰세여? [7][일반] 에르씨(lchbest10) | 18.09.03추천 0
-
오늘의 문제: Glen [1][일반] 시아닌(kimjg1119) | 18.09.03추천 0
-
오늘의 IOI task를 간략하게 알아보자 (day1) [5][일반] 시아닌(kimjg1119) | 18.09.03추천 3
-
별찍기 11번 for문으로 푼게 자랑. [2][일반] qwer(118.218) | 18.09.03추천 0
-
하 부동소수점 핵노잼... [4][일반] 익명(110.11) | 18.09.03추천 0
-
삼성 c형을 설명하면 [7][일반] 0xrgb(0xrgb) | 18.09.02추천 4
-
여기서 피드백 받은지 한 2주일 된거 같은데 이제야 풀었음[일반] 익명(220.118) | 18.09.02추천 0
-
노트부 너무 후회됨 ㅠㅠ[일반] MeF(skwyun) | 18.09.02추천 0
ㄴ
답을 다항시간에 체크 가능 -> NP
NP-Complete는 모든 NP 문제를 다항시간내에 해당 문제로 리덕션 가능할때를 의미함
보통 증명할때는 SAT이랑 3-SAT이 NP Complete인게 증명되어있어서 거기로 리덕션하면 됨
ㄴ 리덕션이 머에요?
한 문제를 다른 문제로 바꾸는거임