Intereting Posts

What does the value of a probability density function (PDF) at some x indicate?
How to solve integral in Mathematica?
Conjectured value of $\int_{0}^{\infty}\left(\frac{x-1}{\ln^2 x}-\frac{1}{\ln x}\right)\frac{\mathrm{d}x}{x^2+1}$
$\displaystyle\sum_{k=0}^n \frac{\cos(k x)}{\cos^kx} = ?$
Prove that :- $A_n = 2903^n – 803^n – 464^n + 261^n$ is divisible by $1897$ for $n \in \mathbb{N}$
How to show $\omega^n$ is a volume form in a symplectic manifold $(M, \omega)$?
Proof related to breadth first search
How minimally can I cut a cake sector-wise to fit it into a slightly undersized square tin?
Generalised Binomial Theorem Intuition
Sequential space implies countable tightness?
Find maximal number of subsets of the set $U$ such that no one is a subset of another
How to show that $f$ is an odd function?
Knight move variant: Can it move from $A$ to $B$
Proof of Schwarz Formula
Dicyclic group as subgroup of $S_6$?

Let our memory slots be represented by elements of $\Bbb{Z}_p$ for a prime $p$. $k$ memory slots would be $k$ copies of the ring: $R = (\Bbb{Z}_p)^k$. Suppose that for a problem $f : X \to Y$, there are $X \xrightarrow{\phi} R \xrightarrow{\psi} Y$, each map computable in $O(|x|)$ time for each $x \in X$, where $|x|$ is the size of the input (e.g. for integers, $X = \Bbb{Z}$ it’s $|x| \approx \ln (x)$, at least for a subset of integers that will map into $R$ “without trouble”). Let’s work with $k = 1$. Then we need a polynomial $g \in \Bbb{Z}_p[x_1]$ such that $\psi\circ g\circ \phi (x) = f(x)$, for all $x \in X$.

Now, there is a finite set of $x \in X$, say $\{x_i\}$ such that $f(\{x_i\}) = f(X)$, since $\Bbb{Z}_p$ is finite. Well then we want $g(\phi (x_i)) = f^{\leftarrow} (y_i)$, where $y_i = f(x_i)$ and $f^{\leftarrow}$ maps $y_i$ to any of the $\phi(x_i)$ such that $f(x_i) = y_i$. This is doable with the poynomial:

$$

g(z) = \sum_{t = 0}^{p-1} f(\phi^{\leftarrow}(z))(1 – (z – t)^{p-1})

$$

- How to use Warshall's Algorithm
- Efficient way to determine if a number is Perfect Square
- Honest and Deceitful Professors Problem
- Lower bound for finding second largest element
- Writing a GCD of two numbers as a linear combination
- Why does Strassen's algorithm work for $2\times 2$ matrices only when the number of multiplications is $7$?

*(which can be computed in $O(p \ln (p))$ time obviously, I digress…)*

Now suppose that it’s true for $k = n$ memory slots. **Is there an inductive proof to finish this off?**

- Is there any infinite set of primes for which membership can be decided quickly?
- Efficient Algorithm for finding left (or right) Transversal in a Group
- Efficiently partition a set into all possible unique pair combinations
- Find the minimum number of links to remove from digraph to make it acyclic
- To fast invert a real symmetric positive definite matrix that is almost similar to Toeplitz
- Find the number of simple labeled graphs which have no isolated vertices
- Is the Collatz conjecture in $\Sigma_1 / \Pi_1$?
- In how many ways we can place $N$ mutually non-attacking knights on an $M \times M$ chessboard?
- How can we draw $14$ squares to obtain an $8 \times 8$ table divided into $64$ unit squares?
- Representing a number as a sum of k pth powers

No induction needed.

Define $g_i(z_1, \dots, z_k) = \sum_{(a_1,\dots, a_k) \in X’} \left (f(a_1, \dots, a_k)_i \prod_{j=1}^k (1- (z_j – a_j)^{p-1}) \right )$.

It is computable in time at most $O(p^k k^2 \ln(p))$. When $p = 2$ and $k = 100$, that explains why there are some exponential time algos. But not proven yet. We’d need to prove that there exist sets of such polynomials that aren’t computable in poly time.

- Limit evaluation for oscillating function
- Simplifying $\frac{\partial V}{\partial T} \cdot \frac{\partial T}{\partial P} \cdot \frac{\partial P}{\partial V}$
- Why convolution regularize functions?
- Recommendation on a rigorous and deep introductory logic textbook
- A real vector space is an inner product space if every two dimensional subspace is an inner product space ?
- Ways to fill a $n\times n$ square with $1\times 1$ squares and $1\times 2$ rectangles
- computing the series $\sum_{n=1}^\infty \frac{1}{n^2 2^n}$
- If $A^kX=B^kY$ for all $k$, is $X=Y$?
- The group of roots of unity in the cyclotomic number field of an odd prime order
- Meaning of “a mapping factors over another”?
- intersection of the empty set and vacuous truth
- Is there $a,b,c,d\in \mathbb N$ so that $a^2+b^2=c^2$, $b^2+c^2=d^2$?
- 'Free Vector Space' and 'Vector Space'
- Proving that the dot product is distributive?
- Question on morphism locally of finite type