“그렇게나 많이요? 이해가 안 가요. 겨우 40개인데 컴퓨터가 느림보가 되다니요.”

그래프의 특성을 따지지 않지. 오로지 거북이처럼 제 갈 길만 가

는 거야. 좀 빠른 거북이이기는 하지만 스스로 생각하지 못 한다 는 치명적인 단점이 있단다. 그런데 이런 컴퓨터의 양면성과 관

련하여 재미있는 문제가 있단다.

“그게 Bea?

혹시 NP 문제라고 들어 봤니?

‘NP 문제요? 처음 들어 봐요.”

당연히 그럴게다. 곱셈이나 덧셈 같은 계산을 1회 시행할 때

컴퓨터도 시간이 필요하지. 물론 그 시간은 매우 짧은 순간이지

re

ro

만 분명 걸리는 시간이 있어. 그 시간을 0.00014 즉 만 분의 1초 라고 하자. 만 번을 시행해야 1초라는 시간이 걸리지. 그럼 25] 시행하면 만 분의 247} 되지. 컴퓨터는 정말 빨리 계산하는 거 야. 그렇지? 그런데 말이다. 4개의 꼭짓점을 갖는 그래프의 착색

TS 구하는 데 필요한 AA 횟수는 2S 네 빈 곱한 Aes a