# Tag Info

13

Here I assume $0\in \mathbb N$. If you disagree start with $105$. Let $S$ be the sequence of numbers of the form $3^i5^j7^k$. Our task is to generate these numbers in order. Apart from $1$ each number added is of the form $3\cdot x$, $5\cdot y$ or $7\cdot z$ where $x,y,z$ are previous numbers in the sequence. We can generate $S$ by shifting $x,y,z$ along ...

11

The concept you are looking for is called enumeration complexity, which is the study of the computational complexity of enumerating (listing) all the solutions to a problem (or the members of a language/set). Enumeration algorithms can be modeled as a two step process:a precomputation step and an enumeration phase with delay. Both of these steps have their ...

8

The number of such images is exponentially large in the dimensions of the image (even after taking into account symmetries), and grows enormous rapidly. For all but very small images, no, it's not feasible to enumerate all such images within the lifetime of the solar system. (There's something wrong with your reasoning if you've concluded it's reasonably ...

7

First of all, the answer that applies here was already given by Raphael in the comments to the question: "Given that we don't even know how to find one simple shortest path in linear time, I doubt it." In the following, thus, I will assume you are interested in knowing about the best available algorithms in the current state of the art. In the following, I ...

6

Consider a weighted, directed graph, with a vertex $v_i$ for $i\in\mathbb{N}$. There is an edge with weight $j-i$ from $v_i$ to $v_j$ if $j\in\{3i,5i,7i\}$. Now run Dijkstra's shortest path algorithm. It will expand exactly the nodes from your sequence and do so in order. This gives an $n\log n$ algorithm to enumerate the first $n$ elements, since the graph ...

6

You can solve this with a priority queue. Let $L(x)$ be the log-probability of the vector $x$, i.e., $$L(x) = \log \prod_i p_i^{x_i} (1-p_i)^{1-x_i} = \sum_i \ell_i(x_i)$$ where $$\ell_i(b) = \log (p_i^b (1-p_i)^{1-b}).$$ Since the log is monotone, your problem is equivalent to looking for a way to enumerate the vectors $x \in \{0,1\}^n$ in order of ...

6

It sounds extremely inefficient compared to floating point. We have a very good understanding of how to control the errors in floating-point calculations (e.g., adding small numbers before large ones, avoiding taking the difference of large numbers and so on) so the only benefit of the methods you're suggesting would appear to be that they offer increased ...

5

I can't make heads nor tails from what you attempt to do, but I know that the answer to your question is: no, NP is not enumerable. First, let's fix what that means. I assume you are asking if $\qquad\displaystyle \mathrm{TM}_{\mathsf{NP}} = \{ \langle M \rangle \mid L(M) \in \mathsf{NP} \}$ is recursively enumerable. It's not by the extended Rice theorem ...

5

You can solve this problem using a recursive formulation of print all paths from a point $(i,j)$ to the target $(n,n)$ in the grid. I call this function $f(i,j)$. So the all paths will be in $f(0,0)$ call. $f(i,j) = \begin{cases} \emptyset & if\ \ {i>j}\\ \emptyset & if\ \ \neg( {0\leq i\leq n\ \wedge 0\leq j\leq n) }\\ \{(n,n)\} & if \ \ i = ... 5 You can use a sieve to enumerate all prime numbers up to$n$. There are multiple algorithms; see the Wikipedia article I link for some examples. The sieve of Atkin and wheel sieves apparently run in$O(n)$time. 5$g$is total computable by definition. By assumption$f : \mathbb{N}^2 \to \mathbb{N}$is total computable.$1$certainly is.$+$certainly is. The concatenation of$+$and$f$is computable by construction, and that's$g$. The details depend on the exact definition of "computable" (i.e. the machine model) you use; see e.g. here. So under the assumption ... 4 For the$k$shortest paths, there are algorithms; see for instance here. Enumerating all shortest paths is, however, an inherently costly thing; there may be superexponentially many such paths. 4 Let$P(i, j)$be the number of paths from the start node,$(0,0)$, to the destination node,$(i, j). Then it's easy to see that \begin{align} P(i, 0) &= 1\\ P(0, j) &= 1\\ P(i, j) &= P(i-1,j)+P(i-1,j-1)+P(i, j-1), \text{ if }i,j>0 \end{align} Applying this recursion directly isn't particularly efficient, since you'll wind up making a lot ... 4 It is somewhat more natural to normalize the number of bit changes per step by the number of steps, namely2^n-1$. We can then rephrase your question as follows. Let$\pi$be a random permutation of$\{0,1\}^n$. You are interested in the distribution of $$X = \frac{1}{2^n-1} \sum_{i=0}^{2^n-2} d(\pi(i),\pi(i+1)),$$ where$d$is Hamming distance. We can ... 4 You are asking two questions: How to count "winning groups" up to isomorphism? Which winning groups are realizable as winning coalitions? From the point of view of winning groups, we can assume that each voter always casts all her votes, and the resulting games is known as a weighted voting game. Counting winning groups Your concept of "winning group" is ... 4 Lexicographic order is not such a good order since its order type is not$\omega$. Instead of explaining formally what that means, let me give an example. Consider the language$(a+b)^*$. If you enumerate the words in lexicographic order, you get $$\epsilon, a, aa, aaa, \ldots, ab, \ldots$$ The first$\ldots$signify infinitely many terms. So it isn't ... 4 Suppose that you have arrays$A_1,\ldots,A_d$of sizes$n_1,\ldots,n_d$. The total number of tuples is thus$n_1 \times \cdots \times n_d$. Given a number in the range$1,\ldots,n_1 \times \cdots \times n_d$, you can decipher it into a tuple (I leave this part to you). It now remains to compute a pseudorandom permutation of the numbers$1,\ldots,n_1 \times \...

4

This probably isn't exactly what you're looking for, but perhaps nevertheless interesting. There have been proposals for different kinds of computables, for example these by Bill Gosper: Continued Fraction Arithmetic (hardware support is described at the bottom, for Continued Logarithms). Doing calculations in software with continued fractions has seen ...

4

As Rick commented, the first question is asking whether the set of Turing machines that recognize no more 330 strings is computably enumerable. Similarly, the second question is asking whether the set of Turing machines that recognize no less 330 strings is computably enumerable. Let us show that second set is computably enumerable using dovetailing. Let $... 4 The paper you're referring to is using "enumeration" just to mean "ordered list". Your feeling that such a list can't be computed by a Turing machine is correct. However, the list exists, even though there's no algorithm that will tell us what its members are. Also, note that it refers to "an enumeration of halting Turing machines", not "an enumeration of ... 3 One approach would be to enumerate all graphs of a given size, then test each one to see if it is planar and filter out the non-planar ones. This might work acceptably if you only want very small graphs. Brendan McKay has a collection that enumerates all non-isomorphic planar graphs of size up to 11, which you could download and use directly. There are ... 3 Here's another way of looking at the problem: You have a lattice generated by the columns of$M$. Use the Lenstra–Lenstra–Lovász (LLL) algorithm to obtain a reduced basis of this lattice. If you replace$M$by a new matrix formed by the output of LLL, then the columns of$M$will still generate the same lattice, but the basis vectors will be closer to being ... 3 Idea: Root the tree in an arbitrary node. For every node, count paths in its subtrees, paths that start in a subtree and end in the root, and paths that start in one subtree, traverse the root and end in another subtree. That is, for a given node$v$with children$u_1, \dots, u_m$, the number$p(v,k)$of paths of length$k$(counting nodes) in the ... 3 Multitape machines are equivalent to single tape machines. You can simulate several tapes on a single tape. In particular, in order to simulate the "print state" model using the "write-only output tape" model, you simulate an extra output tape, and whenever the print state is reached, you copy the contents of the extra output tape to the write-only output ... 3 Use recursion. Something like this: def f(l, k): if l==0: yield [] else: for i in range(k): for L in f(l-1, k): yield [i]+L Here f(l, k) produces all lists of length l all of whose entries are in the range 0..k-1. The idea is that if you have all lists of length l-1 (the output of f(l-1, k)) you can use ... 3 It's not possible to solve this problem "efficiently". There can be exponentially many paths of a given length, so enumerating all of them is not feasible in large graphs. Your dynamic programming approach is a pretty good one, though you might be able to improve it by not storing the paths explicitly but instead storing the paths as linked lists or using ... 3 The answer is the coefficient of$x^N y^M$in the generating function $$\frac{1}{1-x-y-xy}.$$ This is because $$\frac{1}{1-x-y-xy} = \sum_{\ell=0}^\infty (x+y+xy)^\ell,$$ and every term in the expansion of$(x+y+xy)^\ell$corresponds to a walk of length$\ell$. We can also obtain an explicit formula for it:$$\sum_{t=0}^{\min(N,M)} \frac{(N+M-t)!}{t!(N-... 3 Solution: Modify Johnson's algorithm Johnson's algorithm can be used to enumerate all cycles in$G$. It can be easily modified to enumerate only and all the cycles that contain$v$. Johnson's algorithm works by numbering the vertices from$1$to$n\$, and classifying each cycle according to the smallest-numbered vertex in the cycle. It first enumerate all ...

3

Your problem is NP-hard. It's basically a variant of SAT. You shouldn't expect any algorithm that is provably efficient. Instead, I recommend you use an off-the-shelf SAT solver; since your problem is basically SAT, that's probably about as good as you can do, without a lot of effort tuning for your particular scenario. NP-hardness: In particular, if ...

3

After conducting more research I did find a solution, but first I will examine solutions suggested by posters and considered by myself and review why they didn't work. This problem reduces to finding all chordless cycles in a planar graph. This was one of my first thoughts early on, but this doesn't work when you consider the following: 5-------f----...

Only top voted, non community-wiki answers of a minimum length are eligible