Questions tagged [computer-science]
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.
622
questions
16
votes
2
answers
2k
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
962
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 $\{x_1,\dots,x_k\...
4
votes
5
answers
2k
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
2k
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
669
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 ...
17
votes
3
answers
3k
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? ...
50
votes
8
answers
24k
views
Problems known to be in both NP and coNP, but not known to be in P
One such problem I know is integer factorization.
What are other interesting cases?
2
votes
2
answers
230
views
Indexing schemes of binary sequences
I am looking for "low-complexity" indexing methods to enumerate binary sequences of a given length and a given weight.
Formally, let $T_k^n = \{x_1^n \in \{0,1\}^n: \sum_{i=1}^n x_i = k\}$. How to ...
3
votes
0
answers
404
views
Inversion density: Have you seen this concept?
Let $n > 1$ be an integer.
Let $A$ be an array, indexed from $1$ to $n$, of $n$ values
$A(i)$ coming from the finite set $\{0,1\}$.
(More generally, the values can come from any
totally ordered ...
0
votes
1
answer
183
views
Building optimal rewriting rules.
Please give me some pointers where I can learn more about the following problem:
I have two alphabets A and B. A have a dictionary which contains words in A together with their translation in B (ie. ...
1
vote
1
answer
449
views
Algorithm for generating a size k error-correcting code on n bits
I want to generate a code on n bits for k different inputs that I want to classify. The main requirement of this code is the error-correcting criteria: that the minimum pairwise distance between any ...
6
votes
3
answers
2k
views
Software for Tree-Decompositions
Does anybody know about software that exactly calculates the tree-width of a given graph and outputs a tree-decomposition? I am only interested in tree-decompositions of reasonbly small graphs, but ...
1
vote
1
answer
253
views
$\omega$-monoids
Does the notion of $\omega$-monoid exist, analogous to the notions of $\omega$-groupoid and $\omega$-category? If so, some references would be appreciated.
This is an attempted rephrasing of question:...
41
votes
10
answers
7k
views
What is the shortest program for which halting is unknown?
In short, my question is:
What is the shortest computer program for which it is not known whether or not the program halts?
Of course, this depends on the description language; I also have the ...
7
votes
1
answer
354
views
How long are the certificates produced by the Zeilberger and WZ methods for solving combinatorial sums (A=B)?
In the book "A = B" by Petkovesk, Wilf, and Zeilberger, (downloadable here), the authors provide several algorithmic methods for finding closed forms or recurrences for sums involving e.g. binomial ...
1
vote
0
answers
552
views
Cluster-preserving and distance-maximizing embedding into Hamming Space?
I have a set of data, each instance in the real $[0,1]^{d}$. However, it's actually all in a relatively small range around 0.5, clustered into classes in even smaller ranges. The actual origin of the ...
11
votes
1
answer
674
views
I am searching for the name of a partition (if it already exists)
I derived this definition by searching for a representation of a family of sets. I am quite sure that someone should have thought to this before, because it seems to be quite straightforward given a ...
9
votes
0
answers
759
views
Finding a set with the maximum number of finite alphabet strings within a fixed Levenshtein distance of one-another
Please consider the set of all possible strings of some finite size $M$ alphabet $\Sigma$, $\alpha$ $= a_1, a_2, ..., a_k, ..., a_n$, of length $|\alpha| = L$. The Levenshtein distance (or 'edit ...
9
votes
3
answers
1k
views
Non-existence of algorithm converting NP algorithm to P algorithm?
[Edit: in the light of Nate Eldredge's answer below I rephrase the question]
P=NP is equivalent to the existence of a map of the following form:
Input: a polynomial-time non-deterministic Turing ...
1
vote
4
answers
2k
views
What is the name of the function f(x,y) = ((x-1) mod y)+1 ?
Does the function $f(x,y) = ((x-1) \mod y)+1$ have an existing name?
f(1,5) = 1
f(2,5) = 2
...
9
votes
2
answers
1k
views
What are the limits of non-halting?
It's easy enough to build Turing Machines that don't halt. But how complex can we make these? For example, suppose a machine has access to its state transition table and can write to it like a C ...
11
votes
6
answers
2k
views
Uses of bisimulation outside of computer science.
Bisimulation is one of the most important ideas of theoretical computer science. I was wondering whether bisimilarity is used/known outside of computer science/modal logic? I am aware that it ...
4
votes
1
answer
273
views
Is every input gate of a Boolean Circuit (to decide a language) on a path to the output gate?
In complexity theory, when a uniform family of circuits recognises a language is it the case that each of the input gates is on a path to the output gate?
That is, there are no input gates with wires ...
3
votes
4
answers
3k
views
Finding the union of N random circles arbitrarily (or conspiratorially) placed on a two-dimensional surface
Please consider a two-dimensional surface populated with a set of Cartesian coordinates $(x_i, y_i)$ for $N$ circles with individual radii $r_i$, where $r_{\min} < r_i < r_{\max}$.
Here, the ...
5
votes
0
answers
350
views
Chain/Hierarchy of Monoids
Let's assume that we have the following collection of structures:
Some space $P$.
Monoids $(M_{i+1},\circ_{i+1})$, and
Actions $\bullet_{i+1}:M_{i+1}\times M_i\to M_i$, for $i\ge 0$
And $\bullet_{0}:...
16
votes
2
answers
1k
views
What do you use categorical glueing/sconing/Freyd covers for?
In the theory of programming languages and structural proof theory, one of the handiest techniques we have available is a method called "logical relations", in which you can prove properties of ...
1
vote
2
answers
1k
views
Calculating the surface area distribution of two-dimensional projections for a polytope
My question concerns the existence of a nice (deterministic?) method/algorithm for calculating the distribution of surface areas for two-dimensional projections of an arbitrary polytope (or convex ...
9
votes
4
answers
827
views
Characterizing a tumbling convex polytope from the surface areas of its two-dimensional projections
My general question concerns what we can learn about an arbitrary, three-dimensional convex polytope (or convex hull of an arbitrary polytope) strictly from the surface areas of its two-dimensional ...
7
votes
3
answers
3k
views
Emptiness and determinization of NFAs
Consider an NFA on n states. Is it possible to determine whether it accepts all strings in poly(n) time?
Suppose the NFA above has an equivalent DFA on d states. Is it possible to construct this DFA ...
35
votes
14
answers
4k
views
Where have you used computer programming in your career as an (applied/pure) mathematician?
For background: I'm working on a book to help mathematicians learn how to program. However, I need to see some examples from people in the field that have done different kinds of things than I have.
...
17
votes
2
answers
2k
views
Why is Kleene's notion of computability better than Banach-Mazur's?
In this post about the difference between the recursive and effective topos, Andrej Bauer said:
If you are looking for a deeper explanation, then perhaps it is fair to say that the Recursive Topos ...
10
votes
2
answers
603
views
When can a freely moving sphere escape from a 'cage' defined by a set of impassible coordinates?
To ask this question in a (hopefully) more direct way:
Please imagine that I take a freely moving ball in 3-space and create a 'cage' around it by defining a set of impassible coordinates, $S_c$ (i.e....
3
votes
1
answer
3k
views
What is a universal function?
This question stems from Dick Lipton's recent blog post on the Axiom of Choice. I asked there but got no takers. I promise I'm not an inept Googler, but I couldn't find a satisfactory answer. I ...
11
votes
3
answers
1k
views
The difference between the Recursive and the Effective topos.
I would like to know which is the real difference between the Recursive topos (in the sense of Mulry) and the Effective topos (in the sense of Hyland). Especially what is related to recursive ...
4
votes
2
answers
2k
views
Are there any pairing functions computable in constant time (AC⁰)
Are there any known reversible pairing functions $f: \mathbb N \times \mathbb N \to \mathbb N$ that can be computed in constant time (FAC⁰)?
46
votes
7
answers
12k
views
What is the time complexity of computing sin(x) to t bits of precision?
Short version of the question: Presumably, it's poly$(t)$. But what polynomial, and could you provide a reference?
Long version of the question:
I'm sort of surprised to be asking this, because ...
3
votes
3
answers
572
views
The limits of parallelism
Is it possible to solve a problem of O(n!) complexity within a reasonable time given unlimited number of processing units and infinite space?
The typical example of O(n!) problem is brute-force ...
5
votes
3
answers
339
views
Software for Planar Algebras or Group Rings
Does software exists for calculating with planar algebras or group rings? It could be part of Mathematica or be an extension of Python or Java or C. What would go into designing such a data-type ...
7
votes
1
answer
795
views
Counting Eulerian Orientation in a 4-regular undirected graph
We would like to know how hard it is to count Eulerian orientation in an undirected 4-regular graph. For a given edge orientation to be Eulerian, we mean that every vertex has 2 in-edges and 2 out-...
1
vote
2
answers
761
views
Find the subset of a line on a sphere "far" from a set of points on the sphere.
I have some code where the "hot part" relies on an inefficient solution to this problem.
Problem: I have 3 inputs:
a. A collection of N points on the surface of a sphere.
b. A line segment on the ...
50
votes
4
answers
4k
views
What algorithm in algebraic geometry should I work on implementing?
This summer my wife and one of my friends (who are both programmers and undergraduate math majors, but have not learned any algebraic geometry) want to learn some algebraic geometry from me, and I ...
1
vote
1
answer
160
views
Signed minimum?
I am looking for references to papers which might have defined a 'signed minimum' equivalent to
$$smin(x,y) ::= \left(\frac{\textit{signum}(x)+\textit{signum}(y)}{2}\right)\cdot \min(|x|,|y|) $$
where ...
-1
votes
2
answers
1k
views
Travelling Salesman Problem [closed]
Does there exist an instance of the travelling salesman problem where the optimal solution has edges that cross?
11
votes
1
answer
851
views
Counting colored rook configurations in the cube - when is it even?
Informal Statement
In the $n\times n \times n$ grid, we can places rooks (those from chess) such that no two rooks can attack each other. One way to achieve this is to place a rook in position $(i,j,...
13
votes
1
answer
772
views
Bipartite Nim-Geography
Two players are playing a game on a bipartite graph where all of the edges are nim-heaps of various sizes. A token starts on one of the vertices, and on your turn you must move the token over an edge ...
2
votes
1
answer
472
views
Decidable real arithmetic
I believe that what I'm about to describe has a name—I'm almost certain that I've seen this in model theory and term-rewriting systems, possibly having something to do with ‘signature&...
7
votes
5
answers
16k
views
Prove a function is primitive recursive
Hey,
I'm taking a course in computability theory, but I'm struggling with primitive recursion. More specifically we are often asked to prove that some arbitrary function is primitive recursive, but I ...
12
votes
3
answers
873
views
Alive dynamical system
Intuitively, one can say that a dynamical system is alive if one can build a universal Turing machine inside.
So, Conway's Game of Life is alive and shift space should be dead.
I fail to make this ...
3
votes
0
answers
400
views
Wolff's application of CS to analysis
In the foreword of Tom Wolff's "Lectures on Harmonic Analysis", C. Fefferman writes "[Wolff made] (as far as I know) the first serious application of theoretical computer science to analysis." What ...
5
votes
1
answer
2k
views
Finding unknown integer-valued polynomials using inequalities
I've come across this interesting inequalities problem recently, which seemed straight-forward at first glance but has proven interesting enough to ask about it here.
Suppose you are given the ...