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.

Filter by
Sorted by
Tagged with
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 ...
Daniel Litt's user avatar
  • 22.2k
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\...
Marcos Villagra's user avatar
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 ...
John Berryman's user avatar
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!
user7738's user avatar
  • 173
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 ...
Daniel Litt's user avatar
  • 22.2k
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? ...
Dan Ramras's user avatar
  • 8,498
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 ...
gondolier's user avatar
  • 1,829
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 ...
Gerhard Paseman's user avatar
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. ...
danatel's user avatar
  • 173
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 ...
DoubleJay's user avatar
  • 2,353
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 ...
simone's user avatar
  • 85
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:...
supercooldave's user avatar
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 ...
Daniel Litt's user avatar
  • 22.2k
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 ...
Daniel Litt's user avatar
  • 22.2k
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 ...
DoubleJay's user avatar
  • 2,353
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 ...
klaraspina's user avatar
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 ...
Tom Ellis's user avatar
  • 2,775
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 ...
Niall Murphy's user avatar
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 ...
Stanislav's user avatar
  • 101
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 ...
supercooldave's user avatar
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 ...
Niall Murphy's user avatar
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 ...
Rob Grey's user avatar
  • 599
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}:...
supercooldave's user avatar
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 ...
Neel Krishnaswami's user avatar
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 ...
Rob Grey's user avatar
  • 599
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 ...
Aryeh Kontorovich's user avatar
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 ...
Neel Krishnaswami's user avatar
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....
Rob Grey's user avatar
  • 599
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 ...
I. J. Kennedy's user avatar
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 ...
Doctor Gibarian's user avatar
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⁰)?
Niall Murphy's user avatar
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 ...
Ryan O'Donnell's user avatar
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 ...
psihodelia's user avatar
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 ...
john mangual's user avatar
  • 22.6k
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-...
Sangxia Huang's user avatar
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 ...
John's user avatar
  • 13
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 ...
Jacques Carette's user avatar
-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?
bob's user avatar
  • 7
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,...
miforbes's user avatar
  • 1,088
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 ...
zeb's user avatar
  • 8,533
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 ...
Peter Marsh's user avatar
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 ...
Anton Petrunin's user avatar
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 ...
Mark Lewko's user avatar
  • 11.7k
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 ...
Anthony Peterson's user avatar

1
9 10 11
12
13