한때나다 NP hard 논문을 썼던 인간으로써... 어제 헛소리 한 것도 있고 해서 새로운게 나왔다길래 저도 심심풀이로 SICOMP 논문을 살펴보았습니다. 99년에 발표된 A Randomized Fully Polynomail Time Approximation Scheme for the All-Terminal Network Reliability Problem, Dabid R. Karger 이거 읽어보세요. SICOMP volume 29입니다... number라는 것은 solution의 갯수를 의미하는군요. 예를 들자면 이런 문제입니다. 'Given a graph, how many distinct Hamiltonian circuits does it have?' 즉, NP는 '있냐 없냐.. 어쩌냐..' 의 decision의 문제라면 #P 는 '몇개냐?' 라는 counting 문제라고 합니다. 복잡도는, 증명하기는 어려울 듯 한데, NP나 #P나 삐까삐까 하지 않을까 싶네요.