| [ sciEncE ] in KIDS 글 쓴 이(By): guest (123) <211.44.128.120> 날 짜 (Date): 2000년 5월 30일 화요일 오후 11시 36분 48초 제 목(Title): Re: DNA에서 난문해결-암호연구 등에 응� 3-SAT : 3-satisfiability 문제 (맞죠?) 아마 3-CNF (conjunctive normal form) 이라고도 할 겁니다. 쉽게 말해, (a1 | a2 | a5) & (a2 | a3 | a4) & (a4 | a8 | a9) & ...... 이런 식으로 boolean 변수 a1..aN과, 이들의 조합으로 위와 같은 형태로 이루어진 논리식이 있습니다. 이때 이 논리식을 참으로 만들 수 있는 a1..aN의 조합이 존재하느냐 하는 문제지요. (좀 대충대충 쓴 것 같군요. formal하게 정의를 해야겠지만 귀찮아서... -.-) |