#P-Complete

A problem is #P-complete if and only if it is in #P, and every problem in #P can be reduced to it by a polynomial-time counting reduction.

難嗎，其實還好，定義看上去很簡單，只是要找到問題有點難。#P-Complete的難度比起NP-Complete的難度，是在之上，或是和此問題的一樣難。

證明的流程如下：

找一個polynomial-time的function使得這個問題的(每一個)解，可以使用這個function對應到另一個己被證實的#P-complete上面。

看起來和NP-Complete很像對吧。難度在於"每一個"解。也就是說#P的意思在於counting all solutions.

# = number就對啦...

目前已被證實為#P-Complete的問題並不多，因為要找到一個NP-Complete的解就不簡單了，更何況是算出有多少解。 

這裡有一個迷思就是，我可以不用知道所有的解，而算出解的個數嗎!?

也許這是另一種解#P-Complete的方法，但是.還是沒有人提出這樣的證明，因為#P-Complete的難度，至少有NP-Complete這麼難...

研究所二年級時，每天都在看這問題..看過的有..

Counting LCS is #P-complete. Counting random walk solutions is #P-Complete. Counting SAT solutions is #P-Complete.

所以我們幾乎可以說，只要一個問題是NP-Complete，那麼記算他所有的解"應該"就是#P-Complete。至於為什麼用應該呢？因為上面有說過了，說不定有公式求個數解..

於是，只要找到一個plynomial time的解法解出#P-Complete，那麼NP=P, P=PH..

哪有可能找到..2SAT不落於NP-Complete但Counting 2SAT都是#P-Complete了..所以難度的成長快很多..還是等哪位天才快來證明NP!=P吧..