**9**

votes

**1**answer

2k views

### All-pairs shortest paths in trees?

This is a reference request, since I'm sure what follows isn't new, but I can't seem to find it.
Suppose that we have a finite tree $T$ with non-negative weights on the edges. Naively, computing the ...

**4**

votes

**1**answer

349 views

### Injections to binary sequences that preserve order

Suppose we have a countable set S with a total order. Can we give an injection from S to the set of finite binary sequences that end in all zeros that preserves the ordering? The order on binary ...

**3**

votes

**2**answers

334 views

### Finding the solution to b = Ax that minimizes the Hamming weight (everything over the field F_2).

Is there an efficient algorithm for finding the solution $x$ of
$b = Ax$
that minimizes the Hamming weight of $x$, where
$A$ is a nxm-matrix over the field $\mathbb{F}_2$ ("integer matrix modulo ...

**5**

votes

**2**answers

467 views

### A Query regarding the Halting Problem (Omega): Halting Probability for Given Input Size

I was studying the Halting Problem in context of the Probability and had a few doubts regarding it. Hope someone could help me out.
I am aware of the probability of a Random program halting on a ...

**5**

votes

**3**answers

524 views

### Appropiate models of numerical computation

Hello,
in contrast to the more discrete part of computational mathematics (cryptography, combinatorial computation), numerical mathematics seems to ignore typical questions of theoretical computer ...

**4**

votes

**1**answer

243 views

### Turing Machine which generates order on the set of its states

This question is related to this one Do Turing Machines generates any nontrivial lattice on the set o symbols or states?
The Turing machine (TM) is an abstract model for effective implementation of ...

**1**

vote

**1**answer

211 views

### Do Turing Machines generates any nontrivial lattice on the set o symbols or states?

Second question, probably better: Turing Machine which generates order on the set of its states
I would like to ask ( if it is not terribly obviously wrong):
Do Turing Machine generates ...

**1**

vote

**2**answers

278 views

### Positive & Negative Arity

Hi,
You can talk about the arity of a function or an operation - something like addition could have an arity of 2, and negation usually has an arity of 1.
A paper I am reading is talking about ...

**2**

votes

**2**answers

701 views

### viewing the second fundamental form as a tensor

Dear all,
Thank you for your time reading this post. I am a student in computer science so this viewpoint of the second fundamental form may be interesting to you.
I would like to understand the ...

**3**

votes

**2**answers

1k views

### finding numbers at k hamming distance

Guys,
I have N < 2^n randomly generated n-bit numbers stored in a file the lookup for which is expensive. Given a number Y, I have to search for a number in the file that is at most k hamming ...

**8**

votes

**5**answers

416 views

### Syntactically capturing complexity classes

Primitive recursive functions are syntactically constructible in the sense that from a set of "axioms" we can build every function in the set $PR$. This basicly means that we can build a machine that ...

**1**

vote

**1**answer

252 views

### Can a polynomial size CFG describe the finite language \{$w \pi(w)$ : $\pi(w)$ is fixed string permutation, $|w|=n$ is fixed\} over alphabet \{0,1\}?

Can a polynomial size Context free grammar describe the finite language {$w \pi(w)$ : $\pi(w)$ is fixed string permutation, $|w|=n$ is fixed} over alphabet of {0,1}?
One case this is possible is when ...

**4**

votes

**1**answer

474 views

### What fails when using call/cc as realizer of the Peirce formula

Define the axiom constants $p_{A,B}^{((A\rightarrow B)\rightarrow A)\rightarrow A}$ as realizers of the Peirce formula, and $f_A^{\bot\rightarrow A}$ as realizers of the Ex Falso Quodlibet. Then ...

**0**

votes

**0**answers

384 views

### Applications of the property of Kendall-Mann numbers

I am looking for an application of the Kendall-Mann sequence (KM) which uses the property $M(n+1)/M(n) = n - 1/2 + O(1/n)$ ($n \to \infty$) in science ( computer science ( sorting), physics, biology ...

**28**

votes

**17**answers

6k views

### Computer Science for Mathematicians

This is a big-list community question, so I'm sorry in advance if it is deemed too soft but I haven't seen anything similar yet.
I've seen computer scienctists post questions looking to learn things ...

**1**

vote

**2**answers

739 views

### Verifying a sequence that converges to pi [closed]

A computer program ouputs the digits of $\pi$ by evaluating the recurrence relation
$a_{n+1} = a_n + sin \ a_n$
with $a_0 = \frac{6}{5}$
Does the sequence actually converge or is this just ...

**5**

votes

**1**answer

395 views

### What is the pathwidth of the 3D-grid (mesh or lattice) with sidelength k?

This question is now also on http://cstheory.stackexchange.com/questions/4081/what-is-the-pathwidth-of-the-3d-grid-mesh-or-lattice-with-sidelength-k, where a discussion started, and one reference ...

**4**

votes

**2**answers

595 views

### Coloring edges on a graph s.t. the set of edges for any two vertices have no more than 'k' colors in common

Please imagine the case where one has a planar graph, $G$, with a set of $|V|$ vertices, $(v_1, ..., v_{|V|}) \in V$, and $|E|$ edges, $(e_1, ..., e_{|E|}) \in E$. Now, provided a total of $N$ ...

**8**

votes

**3**answers

2k views

### n-dimensional voronoi diagram

Hi, I need to compute the voronoi diagram of a set of points in $R^n$.
I'm quite unschooled on the topic, could someone point me to the right references so that I can
a) understand the theory behind ...

**5**

votes

**1**answer

354 views

### Are innermost reductions perpetual in untyped $\lambda$-calculus?

Background
In the untyped lambda calculus, a term may contain many redexes, and
different choices about which one to reduce may produce wildly
different results (e.g. $(\lambda x.y)((\lambda ...

**2**

votes

**3**answers

320 views

### Can we uniquely define a graph to have the topology of a polytope via proper edge length selection?

I'll ask you to consider a situation wherein one has a series of edges for a graph, $(e_1, e_2, ..., e_N) \in E$, each with a specifiable length $(l_1, l_2, ..., l_N) \in L$, and the goal is to insure ...

**15**

votes

**7**answers

1k views

### Between mu- and primitive recursion

It is well known that primitive recursion is not powerful enough
to express all functions, Ackermann function being probably the best
known example.
Now, in the logic courses (that I have had look ...

**5**

votes

**1**answer

335 views

### Drawing graphs on circles

Please consider the following problem:
Given: a simple graph (without self-loops and without multiple edges) $G$ on $n$ vertices.
Task: place equidistantly the vertices of $G$ on a circle of unit ...

**5**

votes

**1**answer

3k views

### Meaning of \Subset notation

The symbol $\Subset$ (occurring in places where $\subseteq$ could occur syntactically) comes up frequently in a paper I'm reading. The paper lives at the intersection of a few areas of math, and I ...

**29**

votes

**1**answer

3k views

### An edge partitioning problem on cubic graphs

Hello everyone,
I already asked this question on the TCS Stack Exchange, but it has not been resolved yet. Maybe readers of this forum will have other ideas or information, although I suspect that ...

**6**

votes

**1**answer

430 views

### post correspondence problem variant

Is there an algorithm which takes as input two lists of words $v_1,...,v_n$ and $w_1,...,w_n$ over an alphabet $X$ and decides if there is an infinite sequence $(k_i)$ where $1 \leq k_i \leq n$ for ...

**4**

votes

**3**answers

1k views

### Optimal packing of spheres tangent to a central sphere

Please consider a central, ordinary 2-sphere $S_1$, of some radius $r_1$, and a second ordinary sphere, $S_2$, of radius $r_2$, where $r_2 \leq r_1$.
My question concerns optimal values for the ...

**0**

votes

**3**answers

297 views

### boolean functions and averaging / counting

Hey guys,
I have a slightly imprecise question. I would like say something about a whole set of binary strings evaluated by a binary function by just looking at some type of average. The easiest ...

**1**

vote

**2**answers

799 views

### What is the right citation for the power iteration method to find eigenvalues?

What is the right citation for the power iteration method to find eigenvalues, if I want to cite the method in a paper? I've seen some Google PageRank references in this context. But Brin and Page ...

**2**

votes

**4**answers

748 views

### Enumerative algorithm through inclusion-exclusion

Hello everybody !
I wondered, without really knowing where to search, whether there was a "smart" way to enumerate/iterate over all the elements of a set which can be counted by inclusion-exclusion. ...

**3**

votes

**1**answer

472 views

### Approximating an integral representation of the Number Partition Problem

One can write out an integral whose solution gives the number of solutions to the NP-Complete Number Partition Problem and I'm wondering if anyone has an suggestions or ideas on who to solve or ...

**2**

votes

**0**answers

257 views

### Integer relation detection for Subset Sum or NPP?

Is there a way to encode an instance of Subset Sum or the Number Partition Problem so that a (small) solution to an integer relation yields an answer? If not definitely, then in some probabilistic ...

**2**

votes

**0**answers

184 views

### Constructing hard inputs for the complement of bounded halting

If there is always a hard input for the complement of bounded halting, can that input be constructed?
More precisely, suppose that
for any deterministic TM $M$ accepting
$$
...

**8**

votes

**1**answer

869 views

### Expected number of steps for a discrete random walk to visit every point on an N-dimensional rectangular lattice

Please imagine a discrete random walk on an N-dimensional rectangular lattice with dimensional lengths $(l_1, ..., l_N) \in L$ and total lattice points $P = \prod{l_i}$, for $i = 1, ..., N$. At each ...

**1**

vote

**2**answers

980 views

### post correspondence problem

I have read a couple of proofs for the undecidability of the post correspondence problem, but neither reference gave a concrete example of two lists of words over a fixed alphabet such that the ...

**1**

vote

**2**answers

822 views

### Practical use of probability amplification for randomized algorithms

Normally a 2-sided error randomized algorithm will have some constant error $\varepsilon < 1/2$. We know that we can replace the error term for any inverse polynomial. And the inverse polynomial ...

**2**

votes

**1**answer

291 views

### Approximating a recursively-defined function

Let $$f(k) := \frac{2k-1}{k}\bigl(1-\sum\limits_{i\lt k}\frac{i\ f(i)}{k+i-1}\bigr)$$ for $k\in\mathbb{N}^{+}$.
So $f(1) = 1$, $f(2) = 3/4$, $f(3) = 35/72$, etc.
(This function arises when ...

**4**

votes

**3**answers

897 views

### Complete problems for randomized complexity classes

It is believed that $BPP$ has no complete problems. Even for $BPP^O$ for a suitable oracle $O$ it is believed not to have complete problems, unless P=BPP. I wonder if the class MA (the randomized ...

**10**

votes

**3**answers

644 views

### Complete Extensions of First Order Logic (or Language)

Lindstrom's theorem states that any extension of FOL more expressible than FOL fails to have either compactness or Lowenheim-Skolem. When I first read Lindstrom's theorem my first reaction was: "Does ...

**1**

vote

**0**answers

367 views

### Minimizing quadratic form over permutations

Let $Q$ be an $n \times n$ real symmetric matrix and $x$ an $n \times 1$ real vector. Consider the following minimization problem:
$\min_{\pi \in S_n} ~(\pi x)^{\rm T} Q (\pi x)$,
where $S_n$ ...

**6**

votes

**2**answers

883 views

### Bijective proof of weak form of Stirling's approximation

There are short and sweet proofs of various forms of Stirling's approximation. But even the sweetest among them don't instill the same conviction in the reader as a direct bijective proof.
Computer ...

**2**

votes

**2**answers

334 views

### Efficient computation of AB^-1 for matrices

Hi there,
Sorry if this has already been asked before. I tried googling for it, but perhaps I could not find the right words to search for. My question is: Which is the fastest way to compute ...

**29**

votes

**3**answers

4k views

### Can we cover the unit square by these rectangles?

The following question was a research exercise (i.e. an open problem) in R. Graham, D.E. Knuth, and O. Patashnik, "Concrete Mathematics", 1988, chapter 1.
It is easy to show that
$$\sum_{1 \leq k } ...

**6**

votes

**5**answers

2k views

### Aren't “oracle machines” unsound concepts?

From Wikipedia (bold emphasis at the end is mine):
In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as ...

**14**

votes

**2**answers

1k views

### Structure theorems for Turing-decidable languages?

Languages decidable by weak models of computation often have certain necessary characteristics, e.g. the pumping lemma for regular languages or the pumping lemma for context-free languages. Such ...

**1**

vote

**1**answer

421 views

### Number of subset sums

Let $\mathbb{F}_q$ be a finite field with characteristic $p$ and $p < q$ (i.e. not a prime field). Let $D\subseteq \mathbb{F}_q$ be a some set with $|D|=n$. Find a non-empty subset ...

**3**

votes

**4**answers

1k views

### Does an “efficient” random number generator exist?

Given some number $n$ and a seed number $s$<$n$, I want a random number generator (RNG) that will go through all integers `<$n$ before coming back to $s$. The resulting random number must be ...

**4**

votes

**7**answers

1k views

### How to generate a net on a 8-dimensional sphere

Using Matlab, how to generate a net of 3^10 points that are evenly located (or distributed) on the 8-dimensional unit sphere?
Thanks for any helpful answers!

**8**

votes

**4**answers

506 views

### What is the relationship between “translation” and time complexity?

Consider the problem of deciding a language $L$; for concreteness, say that this is the graph isomorphism problem. That is, $L$ consists of pairs of graphs $(G, H)$ such that $G\simeq H$. Now the ...

**13**

votes

**3**answers

1k views

### What is the history of the Y-combinator?

Inspired by the comments to this question, I wonder if someone can explain the history of the fixed point combinator (often called the Y combinator) in lambda calculus.
Where did it first appear? ...