# Tag Info

15

Consider the finite multisets $\mathbf{Bag}\:X$. Its elements are given by $\{x_1,\ldots,x_n\}$ quotiented by permutations, so that $\{x_1,\ldots,x_n\}=\{x_{\pi 1},\ldots,x_{\pi n}\}$ for any $\pi\in\mathbf{S}_n$. What is a one-hole context for an element in such a thing? Well, we must have had $n>0$ to select a position for the hole, so we are left with ...

6

I don't think there's any general algorithm that works for arbitrary semirings. The requirement to be a semiring doesn't give us a lot to work with. However, if you have a closed semiring, then there are algorithms for solving systems of linear equations over the semiring. Closed semirings A closed semiring is a semiring with a closure operator, denoted $... 4 There is a non-trivial randomized algorithm that can solve this in$O(n^2 \log (1/\delta))$time, where$\delta>0$is the desired error probability. See Verification of Identities. Sridhar Rajagopalan and Leonard J. Schulman. SIAM Journal on Computing, 29(4), pp.1155-1163. 3 Interesting question. Factorization of functions, including factorization of polynomials is in fact a classical problem throughout history of mathematics. For the sake of contradiction, assume that $$x^2 + y^3 - e^{z} = f(x)*g(y)*h(y,z)$$ For the sake of simplicity, assume that$f, g, h$are continuously differentiable inside$D$, the place where we are ... 3 There is really no theory behind it: operator precedence is a purely human construct. The reason is that expressions are not linear blocks of text. They are trees. For example, you can represent any arithmetic in Reverse Polish Notation. In a tree, there is no ambiguity. An operator acts on its children, end of story. Humans are good at reading things ... 3 How about the infinite sum $$\sum_{i, j \in \mathbb{N}} X^i ?$$ The derivative is $$\sum_{i, j \in \mathbb{N}} \underbrace{X^i + \cdots + X^i}_{i+1}$$ which is equal to the original by associativity and commutativity of sums. Also, the infinite sum is equal to$\sum_{j \in \mathbb{N}} \mathsf{List}(X)$), so we could try to calculate the derivative using ... 2 Whenever you are faced with two Boolean expressions$f,g$on$n$variables and wish to know whether they are equivalent, there is a simple algorithm you can apply: Go over all$2^n$possible truth assignments, and check whether$f$and$g$have the same truth value on each. While this is infeasible for large$n$, in your case$n = 4$, so there are only ... 2 I assume that in your definition$a \leq b$iff$a + b = b$. First, note that if$a \leq b$and$b \leq a$, then$a = a + b = b + a = b$. Therefore, in order to show that$a = b$, it is sufficient to show that$a \leq b$and$b \leq a$. Now, you want to show that$(a + b)^\ast = (a + ab + b)^\ast$. As explained in the previous paragraph, it is sufficient ... 2 According to Wikipedia, these are two names for the same concept. You can differentiate them by stating that Boolean algebra is an algebraic structure having operations$\land,\lor,\lnot$satisfying certain axioms, and in contrast a Boolean lattice is a lattice having certain properties; but the two definitions are equivalent. Sometimes Boolean algebra and ... 2 Monogenic semigroups. Consider the case of a [monogenic semigroup](monogenic semigroup), that is, a semigroup$S$generated by a single element$s$. If$S$is finite, then it can be totally ordered if and only if it is aperiodic, that is, if there exists a positive integer n such that$s^n = s^{n + 1}$. In this case, the order could be$s \leqslant s^2 \...

1

If $x+1=1$ then, substituting $x'$ for $x$, we deduce that $x'+1=1$. In other words, your claim follows from the fact that $x'$ has the same "type" as $x$.

1

As you mentioned, you can factor $f_1$ and $f_2$ in polynomial time. Consider the multiset $D_1$ of degrees of the factors of $f_1$, and the multiset $D_2$ of degrees of the factors of $f_2$. If $D_1 \ne D_2$, they are not isomorphic. If $D_1 = D_2$, they are isomorphic. That takes care of determining whether they are isomorphic. Computing an ...

1

We can start from $\sin(x)$ which has a nice regular graph. To avoid negative values you can simply use the absolute value $|\sin(x)|$. This produces a graph similar to your but with constant height. To decrease height as $x \to \infty$ we want to multiply that function by something that decrements. For example $\frac{1}{1+|x|}$ goes to $0$ as $x \to \infty$...

1

L. J. Stockmeyer proves that SET BASIS is $\mathrm{NP}$-complete. Reference: L.J. Stockmeyer, The set basis problem is $\mathrm{NP}$-complete, Tech. Report RC-5431, IBM, 1975 Each vector of your problem can be seen as subset of $\{1, 2, \dots, n\}$. And the component-wise OR operation is corresponding to set union. So a basis for a collection of Boolean ...

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