For question borderline with, or having application to, computer science. Consider also posting http://cs.stackexchange.com/ or http://cstheory.stackexchange.com/ instead of here, if appropriate.

learn more… | top users | synonyms

26
votes
0answers
678 views

Computer calculations in A_infinity categories?

Is there a good computer program for doing calculations in A-infinity categories? Explicit calculations in A-infinity categories are an important, useful, yet very tedious task. One has to keep ...
6
votes
2answers
899 views

Busy Beaver - Proof for BB(2) = 4

Hi, I need to prove the above claim. I can show that $BB(2)\ge 4$ by building a turing machine, but how can i show that $BB(2) \le 4$? Searched a lot over the web, and saw that Rado proved it in ...
3
votes
2answers
736 views

Certain type of regular languages

Dear All, there is one type of regular languages, over $\{a,b\}$, which appear naturally in what I am studying, so if anybody could recognise them, or say any sort of their characterisation, that ...
3
votes
2answers
692 views

Kleene's fixed point theorem on recursive subsets of computable functions

I have a question about the possibility to apply/restate the Kleene fixed point theorem on recursive subsets of computable functions. I don't know if this is trivial and/or if related questions have ...
5
votes
1answer
390 views

Arrangement of integers 1..k^2 in k*k grid to minimize energy function

Question arises from considering cache oblivious algorithms. What is the optimal way arrange the numbers $1$ to $k^2$ in a grid, to minimize to average difference between any two neighbouring ...
7
votes
3answers
622 views

Error correcting codes - basic question

Hi, I have a basic question regarding error correcting codes. Suppose I want to encode a finite information $F$ (say a finite string) into a string $x$ of $n$ bits ($n$ can be as large as you want), ...
21
votes
4answers
1k views

A programming language that can only create algorithms with polynomial runtime?

Has someone constructed a programming language that can construct all the algorithms in P, and no others? I'm interested in this restriction coming from the syntax naturally, as opposed to just being ...
2
votes
2answers
562 views

Graph Theory Conjectures [closed]

What are some important conjectures in graph theory that have been checked by computer up to order 11?
6
votes
1answer
328 views

compression of a Turing machine run sequence

consider a Turing machine with a set of states $s_n$ and alphabet symbols $a_n$. now consider a "run sequence" generated from a starting input in the following sense. the run sequence is defined as ...
2
votes
0answers
106 views

How to argue about state transitions?

Computing differs from math by its dependence on state changes, among other things. A program can be seen as a composition of state transitions, and it would be nice to have an inverse function to ...
2
votes
1answer
481 views

Composite finite-state machines

A finite state machine, FSM, is a box with C input/output channels, and S states, and a fixed map $f : S\times C \to S\times C\cup {0}$. If a state $(c_i,s_j)$ is mapped to the 0 element it means it ...
1
vote
2answers
465 views

Is there constructive proof of the fact that every recursive set $A \ne \varnothing$ is recursively enumerable in non-decreasing order?

Every proof I've read about this fact considers two cases: $A$ - finite and $A$ - infinite but this is undecidable problem. So, is there constructive proof?
8
votes
2answers
319 views

Reduction rules for inductive types

(I'm not sure if I should post this here rather than at Theoretical Computer Science, I've found a lot of type theory related questions on MathOverflow) I'm working in Martin-Löf type theory with ...
0
votes
1answer
151 views

Subset-Free Codes

For each non-negative integer $n$, what antichain(s) in $\{0,1\}^n$ with the pointwise partial order: $\;\;$ 1. $\;$ have the most elements $\;\;$ 2. $\;$ minimize the maximum of its elements' sum ...
6
votes
2answers
1k views

Is there any math foundation for map/reduce?

For a while I was thinking that you just need a map to a monoid, and then reduce would do reduction according to monoid's multiplication. First, this is not exactly how monoids work, and second, this ...
4
votes
2answers
208 views

What is the smallest diameter ring a non-convex polyhedron can pass through in 3-space?

The question is mostly in the title. Imagine I have some non-convex polyhedron $P$, and I would like to find the smallest diameter ring that it can pass through in 3-space, undergoing any necessary ...
7
votes
2answers
868 views

Distribution of the computable numbers on the real number line

If we order all the positive computable real numbers $r_1,r_2,r_3...$ by their Kolmogorov complexity in some language $L$, then make a histogram plot of the $r_i$ on the real line, and we scale it ...
12
votes
1answer
2k views

Evidence for integer factorization is in $P$

Peter Sarnak believes that integer factorization is in $P$. It is a well-known open problem in TCS to identify the real complexity class of integer factorization. Take a look at this link for Peter ...
3
votes
1answer
702 views

Decomposition of a complete graph into maximal matching subgraphs

Is there a general way to decompose a complete graph $K_n$ into an union of maximal matching subgraphs such that no two subgraphs share an edge? For example, consider $K_4$ with vertices ...
2
votes
1answer
194 views

Recoving an unknown tree graph with knowledge of root node to leaf node distances

Imagine I have an unknown (undirected) tree graph, $G$, with some unknown number of nodes $||V||$. However, I know the edge-length between nodes is of fixed size, $L_{edge} = 1$, and I have access to ...
4
votes
1answer
241 views

Inverse of Kleisli star, or “extension operator”

While thinking about monads in the theory of denotational semantics, I have made an observation about the Kleisli category that I would like to check Suppose $F : \mathcal D \to \mathcal C$, $G : ...
3
votes
1answer
278 views

Hermit H-machines

I call an H-machine a machine that can be connected to turing machines and that takes as input a natural integer n and instantly returns the n'th digit of the mathematical constant H. Is there a ...
2
votes
2answers
471 views

Threading pinholes in the wall of cylinder to pass through an internal coordinate

Imagine I take a sheet of paper and use a pin to generate an $N$x$M$ rectangular array of small holes. I then fold the sheet to form a cylinder of radius $r_c$ and height $h_c$, where there are $N$ ...
1
vote
1answer
223 views

Is it (believed to be) possible to algorithmically generate Diffie-Hellman tuples without “being able to know” one of the discrete logs involved (formal definition given in question)?

Is it (believed to be) possible, in the various standard examples of groups in which discrete log/Diffie Hellman are hard (including multiplicative groups in modular arithmetic and elliptic curves, ...
1
vote
0answers
129 views

Optimizing for a unique outcome of a probabilistic marriage problem

Let's say I have some number of individuals who are single, $(b_1, ..., b_N) \in B$, and for every possible pairing of two individuals, $b_i$ and $b_j$, I happen to know the exact probability that the ...
0
votes
1answer
179 views

Is there a name for a formula to calculate ascending numbers to a quadratic-like sequence?

For e.g. any range of number 0 - n 0 1 2 3 4 5 6 to: 0 2 4 6 4 2 0 Is there a name for this kind of formula or calculation?
4
votes
3answers
706 views

Estimating the fractal dimension of a point cloud

I have finite set of geolocation point data, and I'd like to estimate the fractal dimension. I know there are several ways to do this, and some of them give different numbers. What is the most ...
2
votes
1answer
315 views

Complexity of computing derivatives

Sorry if this is too simple. This is my first question here. Suppose $f : R^n \to R$ is a differentiable function. Say that we can compute in $T$ arithmetic operations the value $f(x)$ at any point ...
3
votes
1answer
240 views

Numerical Beta Function

Anyone know a fast and concise way of calculating the Beta $B(a,b)$ function for smallish (<10) real $a$ and $b$. For integer $a$ and $b$ I have: $B(a,b) = \prod\limits_{j=1}^b \frac{j}{a+j}$ ...
7
votes
1answer
297 views

RAM simulating another RAM

(Cross-posted from cstheory-stackexchange) The following fact seems to be used implicitly in cs theory, particularly algorithms. Given a RAM machine $M$ running in time $O(f(n))$, another RAM machine ...
0
votes
1answer
546 views

Transition Graph per alphabet?

How do you determine how many different Transition Graphs are over a particular alphabet? For example How many TG's are over the alphabet {x, y}. I am taking a class with a similar question from ...
2
votes
1answer
1k views

How many cpus needed to check a 100 million digit prime number efficiently? [closed]

If I had access to potentially unlimited CPUs and wanted to quickly check 100 million digit numbers for primality using a map-reduce architecture, how many CPUs would be necessary? Each of the mapped ...
1
vote
3answers
364 views

Operator probability in a RPN string

Consider the set $S_n$ of all strings of length $n$ ($n$ integer, $n \geq 3$) representing an expression in RPN ( http://en.wikipedia.org/wiki/Reverse_Polish_notation. ) Assumptions (to simplify): ...
1
vote
2answers
496 views

Hash functions and inner product

Hi all, As a part of a research I'm working on (involving derandomization of linear threshold functions), I'm trying to understand the following problem: Is there a small (polynomial rather than ...
1
vote
1answer
454 views

Decomposing a sphere (or defomed sphere) into a vertex-transitive graph with fixed-length curved edges

Please see the original problem specification (which Joseph O'Rourke was responding to in his answer) below. Motivation - I'm interested in a particular case of the problem where one wants to ...
1
vote
0answers
209 views

Geometric/Analytic techniques for constructive and asymptotic bounds in the Lee metric

Slight extension of cross posting from http://cstheory.stackexchange.com/questions/7408/lee-metric-gilbert-varshamov-and-hamming-bounds-for-larger-relative-distance-rang (closed there) The following ...
1
vote
1answer
258 views

Constructing a graph that approximates a sphere using rotationally symmetric building blocks with equal numbers of edges

I'd like to construct a graph that approximates a sphere in 3-space, but I'm placed under the following constraints: (1) - I am only allowed to use a construction block, $v_i$, consisting of a single ...
6
votes
6answers
3k views

Fast evaluation of polynomials

Hello everybody ! I was reading a book on geometry which taught me that one could compute the volume of a simplex through the determinant of a matrix, and I thought (I'm becoming a worse computer ...
1
vote
1answer
129 views

Inferring geometric properties of a polytope from intersection volumes of spheres at unknown coordinates on its surface

Let's say we have some polytope $P$ in 3-space (which is not necessarily convex) as well as some number of points on its surface, $(g_1, ..., g_N)$. We are provided no information about the ...
1
vote
0answers
343 views

NP-complete variants of NPI problems

Motivated by these posts, An NP-complete variant of factoring and Relationship between symmetry and computational intractability, It seems to be worthwhile to investigate the different factors that ...
8
votes
1answer
459 views

Magma “actions” (or alternatively, “What is the Yoneda lemma for magmas?”)

Arguably the most import thing about groups, semigroups and more generally categories, is that they can act on sets (or even collections of sets in the case of a category). This is the basis for all ...
5
votes
1answer
348 views

Growth zeta-functions of regular languages

Dear All, my following question may be known and ought to be known, so in case it is folklore please could you give me the references. To start, it is obvious that growth of rational languages are ...
7
votes
1answer
561 views

The hardness of computing inverse

Say we have a one-to-one (total) function $f:\mathbb{N}\to\mathbb{N}$ and a Turing-machine $T_f$ that computes it. Suppose further that $T_f$ runs in polynomial time wrt. length of the input. Are ...
2
votes
1answer
284 views

Given a PDA M such that L(M) is in DCFL construct a DPDA N such that L(N) = L(M)

Is it possible to construct an algorithm which takes as input a pushdown automaton $M$ along with the information that the language accepted by this automaton $L(M)$ is a deterministic context-free ...
2
votes
1answer
434 views

Lipschitz constant of Laplace-Beltrami Operator

I already asked this question at stackexchange with no response - so I'll try here. I'm reading a paper on discrete differential geometry: Meyer et.al. They define the Laplace-Beltrami operator at ...
2
votes
2answers
229 views

Correcting bias in samples selected by a prediction

Here is the scenario: I'm trying to find as many golden tickets as I can, so that I can sell them to kids that want to go on a tour of Wonka's chocolate factory. Fortunately, I have a machine that ...
2
votes
1answer
714 views

Official name and complexity of k-way balanced set partitioning? What is the best heuristic?

As a lot of people know, graph partitioning is NP-Complete. In graph partitioning, you try to create k balanced (within some pre-specified epsilon) disjoint subsets of (possibly weighted) vertices ...
2
votes
3answers
2k views

Worst known algorithm in terms of Big-O (more precisely Big-theta)?

Hello, I have been trying to find the worst algorithm in terms of it's Big-O function. By worst I mean n! is worse than n^2, n^n is worse than n!, etc. Essentially the worst algorithm would be the ...
3
votes
2answers
497 views

Partition a square into sub-rectangles with restrictions

Is there an algorithm to generate all partitions of given square by using $n$ vertical and $n$ horizontal lines into sub-rectangles under the following restrictions: 1- No vertical line crosses any ...
0
votes
1answer
158 views

the maximal length of a special dicksonian sequence

First, we define a sequence $t_{1},t_{2},\cdots,t_{k}$ of n-tuples dicksonian, if $\forall 1\leq i < j\leq k,$ there does not exist a non-negative n-tuple t such that $t_{i}+t=t_{j}.$ For example, ...