Hot answers tagged

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


5

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


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