<p>What does #P-complete mean in practice?<br />
The program numsat works on general cnf,
using complete search with components.<br />
I cannot fathom anything but deterministic search.<br />
Any nondeterministic answer would be a poor guess.</p>
<p>Here is some state of the art data,<br />
possible food for theoretical thought...<br />
Can anyone validate growth of these series?</p>
<p>Is #sat of monotone 2cnf #P complete? Yes.<br />
Here is what that means in practice.<br />
100 variables is near the practical limit.<br />
The number of models grows roughly as 2^(2n/3)<br />
The number of assumptions is roughly 2^(n/3)<br />
Components correlate with assumptions.<br />
Inferences are roughly ten times assumptions.<br />
The program is available by email: smith23801530 at gmail dot com<br />
Joseph Daniel Pehoushek</p>
<p>Here are experimental results on random monotone 2cnf.<br />
#a assumptions #c components #i inferences (billions remainder)<br />
Monotone 2cnf two occurrences per variable.<br />
m2d2n10.cnf,   (#P 104 : #a 10 #c 12 (#i 0 87))<br />
m2d2n20.cnf,   (#P 10340 : #a 36 #c 39 (#i 0 349))<br />
m2d2n30.cnf,   (#P 784740 : #a 124 #c 142 (#i 0 1405))<br />
m2d2n40.cnf,   (#P 313679080 : #a 1694 #c 1969 (#i 0 20773))<br />
m2d2n50.cnf,   (#P 16886248407 : #a 2230 #c 2591 (#i 0 27356))<br />
m2d2n60.cnf,   (#P 1548010934229 : #a 3200 #c 3719 (#i 0 39321))<br />
m2d2n70.cnf,   (#P 583600104724728 : #a 452192 #c 525609 (#i 0 5589411))<br />
m2d2n80.cnf,   (#P 44361287415139863 : #a 196216 #c 228073 (#i 0 2425169))<br />
m2d2n90.cnf,   (#P 3340741443818080654 : #a 2443636 #c 2840380 (#i 0 30206260))<br />
c[bigsums (tfiles 9 tforms 9) (numberp 3385687896549602145 zeromos 0)(retros 3099338 bigoh 0 billion 38310131)]<br />
m2d2n91.cnf,   (#P 8838590596190174105 : #a 30693896 #c 35677325 (#i 0 379417564))<br />
m2d2n92.cnf,   (#P 19036965853881143224 : #a 1573169064 #c 1828587185 (#i 19 446489945))<br />
m2d2n93.cnf,   (#P 16371066159636605172 : #a 35428 #c 41178 (#i 0 437553))<br />
m2d2n94.cnf,   (#P 24631033372012180330 : #a 84160 #c 97824 (#i 0 1039971))<br />
m2d2n95.cnf,   (#P 23112230478857377935 : #a 13692 #c 15914 (#i 0 168873))<br />
m2d2n96.cnf,   (#P 146335589705051903772 : #a 54448822270 #c 63289077438 (#i 673 60841893))<br />
m2d2n97.cnf,   (#P 181526497832196124785 : #a 17278 #c 20082 (#i 0 213179))<br />
m2d2n98.cnf,   (#P 414737590951956195798 : #a 17490830 #c 20330623 (#i 0 216209838))<br />
m2d2n99.cnf,   (#P 671053183690751719166 : #a 896455194 #c 1042002744 (#i 11 81394252))<br />
c[bigsums (tfiles 9 tforms 9) (numberp 1505642748640533424287 zeromos 0)(retros 56966781812 bigoh 704 billion 186213068)]</p>
<p>three occurrences per variable<br />
m2d3n10.cnf,   (#P 82 : #a 14 #c 18 (#i 0 170))<br />
m2d3n20.cnf,   (#P 6140 : #a 260 #c 294 (#i 0 3364))<br />
m2d3n30.cnf,   (#P 177408 : #a 878 #c 1022 (#i 0 11198))<br />
m2d3n40.cnf,   (#P 21848783 : #a 8384 #c 9968 (#i 0 109402))<br />
m2d3n50.cnf,   (#P 2999666797 : #a 49810 #c 60229 (#i 0 663636))<br />
m2d3n60.cnf,   (#P 186678215369 : #a 641262 #c 779593 (#i 0 8475401))<br />
m2d3n70.cnf,   (#P 8942241918897 : #a 1080232 #c 1290637 (#i 0 13940124))<br />
m2d3n80.cnf,   (#P 490045501565302 : #a 15036360 #c 17952035 (#i 0 194044109))<br />
m2d3n90.cnf,   (#P 65577822144996044 : #a 130423610 #c 157913680 (#i 1 694727523))<br />
c[bigsums (tfiles 9 tforms 9) (numberp 66076999588394822 zeromos 0)(retros 147240810 bigoh 1 billion 911974927)]<br />
m2d3n100.cnf,   (#P 12107519305305449401 : #a 1173792016 #c 1421447938 (#i 15 224973309))<br />
m2d3n110.cnf,   (#P 583435111918994703426 : #a 4945924512 #c 1677068293 (#i 64 280963526))<br />
m2d3n120.cnf,   (#P 35950128588370803291696 : #a 54134596580 #c 298041404 (#i 698 238705472))<br />
m2d3n130.cnf,   (#P 1470948632659714863050325 : #a 75475643130 #c 1341975296 (#i 976 724138128))</p>

CC BY-SA 4.0
2024-10-27T20:48:31.203Z
2024-10-27T20:48:31.203Z
joseph pehoushek
<p>The whole space must be searched for #P, which appears to require determinism.
Of course, checking the answer is rather difficult.</p>

CC BY-SA 4.0
2024-10-16T14:34:54.960Z
Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking.
Community
<cc.complexity-theory>
Is #sat impossible for quantum computing algorithms?
joseph pehoushek
# Is #sat impossible for quantum computing algorithms?

(Asked by: username_0 on 2024-10-13)

The whole space must be searched for #P, which appears to require determinism.
Of course, checking the answer is rather difficult.

**Tags:** cc.complexity-theory

> **Comments:**
> **username_1**: Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking.  

---

## 1 answers

### Answer by username_0 on 2024-10-27. Score: -1 | Accepted answer

What does #P-complete mean in practice?  
The program numsat works on general cnf,
using complete search with components.  
I cannot fathom anything but deterministic search.  
Any nondeterministic answer would be a poor guess.

Here is some state of the art data,  
possible food for theoretical thought...  
Can anyone validate growth of these series?

Is #sat of monotone 2cnf #P complete? Yes.  
Here is what that means in practice.  
100 variables is near the practical limit.  
The number of models grows roughly as 2^(2n/3)  
The number of assumptions is roughly 2^(n/3)  
Components correlate with assumptions.  
Inferences are roughly ten times assumptions.  
The program is available by email: smith23801530 at gmail dot com  
Joseph Daniel Pehoushek

Here are experimental results on random monotone 2cnf.  
#a assumptions #c components #i inferences (billions remainder)  
Monotone 2cnf two occurrences per variable.  
m2d2n10.cnf, (#P 104 : #a 10 #c 12 (#i 0 87))  
m2d2n20.cnf, (#P 10340 : #a 36 #c 39 (#i 0 349))  
m2d2n30.cnf, (#P 784740 : #a 124 #c 142 (#i 0 1405))  
m2d2n40.cnf, (#P 313679080 : #a 1694 #c 1969 (#i 0 20773))  
m2d2n50.cnf, (#P 16886248407 : #a 2230 #c 2591 (#i 0 27356))  
m2d2n60.cnf, (#P 1548010934229 : #a 3200 #c 3719 (#i 0 39321))  
m2d2n70.cnf, (#P 583600104724728 : #a 452192 #c 525609 (#i 0 5589411))  
m2d2n80.cnf, (#P 44361287415139863 : #a 196216 #c 228073 (#i 0 2425169))  
m2d2n90.cnf, (#P 3340741443818080654 : #a 2443636 #c 2840380 (#i 0 30206260))  
c[bigsums (tfiles 9 tforms 9) (numberp 3385687896549602145 zeromos 0)(retros 3099338 bigoh 0 billion 38310131)]  
m2d2n91.cnf, (#P 8838590596190174105 : #a 30693896 #c 35677325 (#i 0 379417564))  
m2d2n92.cnf, (#P 19036965853881143224 : #a 1573169064 #c 1828587185 (#i 19 446489945))  
m2d2n93.cnf, (#P 16371066159636605172 : #a 35428 #c 41178 (#i 0 437553))  
m2d2n94.cnf, (#P 24631033372012180330 : #a 84160 #c 97824 (#i 0 1039971))  
m2d2n95.cnf, (#P 23112230478857377935 : #a 13692 #c 15914 (#i 0 168873))  
m2d2n96.cnf, (#P 146335589705051903772 : #a 54448822270 #c 63289077438 (#i 673 60841893))  
m2d2n97.cnf, (#P 181526497832196124785 : #a 17278 #c 20082 (#i 0 213179))  
m2d2n98.cnf, (#P 414737590951956195798 : #a 17490830 #c 20330623 (#i 0 216209838))  
m2d2n99.cnf, (#P 671053183690751719166 : #a 896455194 #c 1042002744 (#i 11 81394252))  
c[bigsums (tfiles 9 tforms 9) (numberp 1505642748640533424287 zeromos 0)(retros 56966781812 bigoh 704 billion 186213068)]

three occurrences per variable  
m2d3n10.cnf, (#P 82 : #a 14 #c 18 (#i 0 170))  
m2d3n20.cnf, (#P 6140 : #a 260 #c 294 (#i 0 3364))  
m2d3n30.cnf, (#P 177408 : #a 878 #c 1022 (#i 0 11198))  
m2d3n40.cnf, (#P 21848783 : #a 8384 #c 9968 (#i 0 109402))  
m2d3n50.cnf, (#P 2999666797 : #a 49810 #c 60229 (#i 0 663636))  
m2d3n60.cnf, (#P 186678215369 : #a 641262 #c 779593 (#i 0 8475401))  
m2d3n70.cnf, (#P 8942241918897 : #a 1080232 #c 1290637 (#i 0 13940124))  
m2d3n80.cnf, (#P 490045501565302 : #a 15036360 #c 17952035 (#i 0 194044109))  
m2d3n90.cnf, (#P 65577822144996044 : #a 130423610 #c 157913680 (#i 1 694727523))  
c[bigsums (tfiles 9 tforms 9) (numberp 66076999588394822 zeromos 0)(retros 147240810 bigoh 1 billion 911974927)]  
m2d3n100.cnf, (#P 12107519305305449401 : #a 1173792016 #c 1421447938 (#i 15 224973309))  
m2d3n110.cnf, (#P 583435111918994703426 : #a 4945924512 #c 1677068293 (#i 64 280963526))  
m2d3n120.cnf, (#P 35950128588370803291696 : #a 54134596580 #c 298041404 (#i 698 238705472))  
m2d3n130.cnf, (#P 1470948632659714863050325 : #a 75475643130 #c 1341975296 (#i 976 724138128))


---

