The 2024 Developer Survey results are live! See the results

# Questions tagged [counting]

The term Counting in Computer Science is usually used to refer to counting objects in certain arrangements or with certain properties.

203 questions
Filter by
Sorted by
Tagged with
90 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. ...
• 13.8k
12 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 ...
• 1,891
1 vote
57 views

• 532
66 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?
53 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
188 views

• 173
79 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
511 views

### Complexity of a variant of #Positive-2-SAT

#Positive-2SAT is the problem of counting the number of satisfying assignments to a given Positive 2-CNF formula i.e 2-CNF formulas in which each literal is a positive occurrence of a variable. The ...
• 43
92 views

### Counting States in the trim automaton for $L\circ L'$

Preliminaries. Let $n,m \in \mathbb{N}$. Let our alphabet be $\Sigma = \{0,1\}$, with non-empty languages $L \subseteq \Sigma^n$ and $L' \subseteq \Sigma^m$. We follow the standard definition for ...
• 935
196 views

### Find Number of subsequences such that bitwise OR is same as sum

Suppose there is an array having at most 10 elements between 1 to 10^18. Suppose the array has elements B1,B2,.Bn. We can choose sequence A1,A2,A3,..An such that 0<=Ai<=Bi. Count How many ...
• 1
1 vote
139 views

### fastest algorithm to count leaf nodes (i.e. terminal nodes)

With the following recursive code to count leaf nodes of a binary tree, is there any way to make it faster or parallel-computing optimized in time? Python code - (mag(P) = number of leaf nodes of tree ...
• 119
78 views

• 807
469 views

• 33
1 vote
71 views

### Does the existence of an $\alpha$-approximation scheme for a problem $f$ imply there exists a fully polynomial (deterministic) approximation scheme?

If you have an $\alpha$-approximation algorithm $A$ for some problem $f \in \#P$, such that (for $0 < \alpha \leq 1$) $$\alpha f(x) \leq A(x) \leq \frac{f(x)}{\alpha},$$ does that automatically ...
• 33
1 vote
89 views

### How to count this operation for (int interval = n/2; interval > 0; interval /= 2) using counting primitive operation?

I was confused how to label this for (int interval = n/2; interval > 0; interval /= 2) with counting operation and estimating this operation so that I can get ...
• 23
2k views

### Applications of the DGIM algorithm

In the field of mining of data streams the algorithm of Datar-Gionis-Indyk-Motwani (DGIM, M. Datar, A. Gionis, P. Indyk, and R. Motwani, “Maintaining stream statistics over sliding windows,” SIAM J. ...
• 125
102 views

### Why can’t we use FPRAS for #DNF to estimate #CNF?

Why cant we approximate the number of satisfying assignments of a CNF formula $g$ by first counting the solutions to $\neg g$ (which is in DNF) using the FPRAS for $\#DNF$ and then estimating the $\#g$...
• 173
36 views

### Counting all subsequences constrained to a condition

I was trying to find all subsequences constrained to the following conditions: remove element from the end. remove element from the beginning. remove element from both sides. For example, given the ...
• 515
1 vote
209 views

### Determining the number of reachable vertices from every vertex in a directed acyclic graph

Let $G = (V, E)$ be a directed acyclic graph, which is quite sparse (in the examples I have in mind, $|E| \approx 10|V|$ or so). For each vertex $v \in V$, let $f(v)$ be the number of vertices ...
• 266
1 vote
44 views

### How many functions require precisely $n^2$ gates?

I'm trying to determine an asymptotic bound on the cardinality of the following set of functions. It is the functions with $n$-bit inputs, $\{0,1\}$ output, and requires precisely $n^2$ NAND gates. I'...
• 367
1 vote