| [ QuizWit ] in KIDS 글 쓴 이(By): memory (라면밥말아) 날 짜 (Date): 2007년 5월 10일 목요일 오후 10시 56분 23초 제 목(Title): KOLMOGOROV's PUZZLE Suppose all words, all sequences of characters, are of one of two classes - those that are fit to print (decent) and those that are not (indecent). Now given an infinite sequence of characters, can you always break it into finite sequences so all words except perhaps the first one belong to the same class? 위대한 소련의 수학자 kolmogorov가 고등학교 방문했을때 애들한테 풀어보라고 냈던 문제라고 합니다. 전 잘 모르겠더군요... 다른분들은 푸실 수 있는지 궁금합니다.. 참고로 NP-complete를 만들어낸 Levin이 그 고등학교에 있었는데 이 문제를 풀어서 Kolmogorov가 지도교수가 되서 모스크바 대학에 입학했습니다.. |