New answers tagged computer-science
5
votes
Shifting an irrational binary sequence
I'll prove a general theorem. Unlike in my comments, I won't use any specific theorems.
Let $A$ be a finite alphabet and $X \subset A^{\mathbb{N}}$ a subshift of finite type, or SFT, meaning $X$ is ...
- 6,652
12
votes
Accepted
Shifting an irrational binary sequence
No, there's no irrational $s$ with this property. Here's a concrete hands-on argument. (This may be equivalent to Ville Salo's comment, but I'm not familiar with that terminology.)
The sequence $d = s\...
- 6,486
14
votes
Accepted
Is the set of generalized Fermat triples computable?
Yes. If there are solutions for $1\in\{a,b,c\}$, the equation has the form $a^m\pm b^n=1$, where $\log a/\log b$ is irrational, and decidability follows from strong enough effective lower bound on $|m\...
- 651
3
votes
Problems known to be in both NP and coNP, but not known to be in P
Suppose that $M$ is a triangulated three-manifold. Then deciding if $M$ is homeomorphic to the three-sphere lies in NP and also in co-NP. Its containment in NP is due to Schleimer (see also Ivanov). ...
4
votes
Problems known to be in both NP and coNP, but not known to be in P
This was mentioned in a comment on this answer, but I think it's important enough to warrant its own answer, especially since new results have arisen since then.
A parity game is defined by a directed ...
3
votes
Accepted
References: rigorous algorithms for elementary computations in base-b with complexity estimates
In cryptography, one often needs to implement modular (and polynomial) arithmetic $\mathbb{Z}/N\mathbb{Z}$, but your hardware only natively supports computations in $\mathbb{Z}/n\mathbb{Z}$.
Typical ...
- 2,183
Top 50 recent answers are included