Questions tagged [counting]
The term Counting in Computer Science is usually used to refer to counting objects in certain arrangements or with certain properties.
206 questions
1
vote
1
answer
114
views
Complexity class of a specific counting problem
I have a counting problem that I know is in $\mathrm{GapP}^+$, and if it is in $\#P$ it subsumes another $\#P$-complete problem entirely. I found a solution to the problem that involves identifying ...
- 133
1
vote
0
answers
43
views
Help me understand Valiant's $\#P_1$-completeness reduction
In his paper on the complexity of counting problems, Valiant presents a reduction from a counting nondeterministic Turing machine to a problem he calls $A$-SUBSET-PATTERNS. In this problem, we are ...
- 11
1
vote
1
answer
71
views
Efficient count of upper-right region population
Suppose you're given a population of $n$ points $(x_i, y_i)$ in the unit square $[0, 1]^2$. For a given new sample $(x, y)$, you must find the number of points in the original population satisfying $x\...
- 11
2
votes
1
answer
167
views
Counting number of assignments restricted by implications
Suppose we have $n$ boolean variables, $x_1, \dots, x_n$. Some boolean variables can have implication relationships, e.g. $x_2 \implies x_5$, which means that if $x_2$ is true $x_5$ must also be true. ...
- 14k
2
votes
0
answers
33
views
Are $\#Clique$ and $\#Coloring$ $\#\mathsf P$-hard on perfect graphs?
It is known that decision variants of these problems on perfect graphs are decidable in polynomial time.
But is counting the number of maximum cliques or optimal colorings $\#\mathsf P$-hard on ...
- 2,131
1
vote
1
answer
83
views
How many lower-case 6 letter words can I write so that every pair has exactly two matching letters?
To put it formally, how many 6-letter words with letters from 'a' to 'z' can I write, where for every pair $w_i$ and $w_j$, there are exactly two distinct indices $1\leq a, b\leq 6$ such that $w_i[a] =...
- 173
2
votes
1
answer
417
views
SAT solvers for counting the number of solutions
Are there existing SAT solver libraries that can count the number of solutions of a boolean formula? Can you give examples?
I mean implementations more efficient than the naive approach, i.e. each ...
- 145
0
votes
0
answers
106
views
Growth of the average numbers of peaks for the permutations of $n$ sticks
There are $n$ sticks of lengths $1$ to $n$ in a row. Upon permuting them randomly, we may calculate the average number of peaks viewed from left. A peak is a stick such that all sticks to its left are ...
- 1,038
1
vote
1
answer
83
views
Efficient way to implement a bit-wise counter that becomes 1 every (k*n)+i times
My question is about LeetCode "137.Single Number II":
137.Single Number II
Given an integer array nums where every element appears three times
except for one, which appears exactly once. ...
- 173
2
votes
0
answers
51
views
Windowed LogLog/HyperLogLog algorithm to get a count of the cardinality of the set of the last $k$ elements?
LogLog/HyperLogLog provides a great way for estimating the cardinality of the set of $n$ objects. At its simplest, you hash all $n$ objects into binary strings, find the largest number of leading 0's $...
- 652
-2
votes
2
answers
136
views
Is the set of all strings over $\Sigma$ countably infinite or not?
Let $\Sigma$ be an alphabet. Is the set of all strings over $\Sigma$ (i.e. $\Sigma^*$) countably infinite or uncountably infinite?
- 1
0
votes
0
answers
83
views
formalization of partial function for counting
I need assistance in defining axioms for partial functions in total function theory that is available in Coq.
Specifically, I'm looking for a constructive definition of a partial function that ...
1
vote
4
answers
365
views
XOR pair frequency queries
We are given an array of length $N$ and $Q$ queries (offline) where each query is a value $K$, for each query we need to count number of pairs in array with XOR $K$.
If $N$ and $Q$ can both be upto $...
- 333
1
vote
0
answers
75
views
Is there a known FPRAS for this simple partition function?
I Let $G$ be the set of simple graphs on $n$ nodes. Given a $g \in G$, we denote the number of triangles in $g$ with $n(g)$. Given some positive real-valued parameter $w$, we define the the function $...
- 183
0
votes
1
answer
105
views
Complexity of this variant of #Positive 2-SAT #P-complete?
In this variant of #Positive-2-SAT ,we divide set of all possible clauses like this :
A = [ab ,ac ,ad ,.... ]
B =[bc ,bd ,be ,....]
C=[cd ,de ,....]
D=[de ,....]
....
In this variant ,we are allowed ...
- 43