# Tag Info

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 ...
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 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 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 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 ... 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 ...