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.
641 questions
4
votes
6
answers
751
views
Reconstructing an ordering of a multiset from its consecutive submultisets
We have a multiset $S$ of size $t$ with $r$ distinct elements, where $t$ is much larger than $r$. We want to reconstruct an ordering $s_1, s_2, ... s_t$ of the elements of $S$ given the values of $t$ ...
CommunityBot
- 1
2
votes
2
answers
378
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 A*inv(B)...
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 ...
- 5,502
8
votes
4
answers
680
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 ...
CommunityBot
- 1
1
vote
1
answer
993
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\...
- 33.8k
11
votes
1
answer
860
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,...
CommunityBot
- 1
2
votes
2
answers
249
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 ...
- 21
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 ...
- 495
0
votes
1
answer
185
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. ...
CommunityBot
- 1
1
vote
1
answer
455
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 ...
- 56.6k
1
vote
2
answers
767
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 ...
CommunityBot
- 1
1
vote
1
answer
262
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:...
CommunityBot
- 1
7
votes
1
answer
357
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 ...
- 11.8k
1
vote
0
answers
579
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 ...
- 2,383
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 ...
CommunityBot
- 1
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}:...
- 1,882
12
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 ...
- 1,882
10
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 ...
CommunityBot
- 1
17
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 ...
- 66.8k
4
votes
1
answer
274
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 ...
- 4,729
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 ...
CommunityBot
- 1
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 ...
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 ...
CommunityBot
- 1
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 ...
- 236k
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⁰)?
- 339
3
votes
3
answers
579
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 ...
- 4,729
5
votes
3
answers
348
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 ...
CommunityBot
- 1
7
votes
1
answer
805
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-...
- 17k
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 ...
- 25.2k
2
votes
1
answer
477
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&...
- 12.9k
3
votes
0
answers
404
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 ...
- 13k
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 ...
- 61.9k
1
vote
1
answer
2k
views
Closed form of a nonlinear recurrence sequence.
The master theorem seems to fail on nonlinear recursive functions. Is there a standard tool for finding the closed forms of recursive functions of this form?
The question comes from trying to find ...
- 1,981
3
votes
1
answer
2k
views
Conditions that allow unique solutions for Linear Diophantine equations
(This posting became very long, so I should note that there are two alternative but nearly equivalent formulations of the same question being given. The first one asks for the optimal strategy for ...
CommunityBot
- 1
6
votes
2
answers
605
views
Complexity class of problems solvable using Q&A site
Motivation
We will be trying to find what is the complexity class of problems solvable by a polynomial time algorithm (poster) that has access to a certain oracle (Q&A site) formalizing certain ...
CommunityBot
- 1
5
votes
3
answers
4k
views
Counting lattice points on an n-simplex
Imagine an n-simplex, the solution set for the expression: $a_1$*$x_1$ + $a_2$*$x_2$ + ... + $a_n$*$x_n$ = S, where:
$a_1$ through $a_n$ are positive bounded integers
$x_1$ through $x_n$ are ...
- 43
1
vote
1
answer
210
views
Extracting integer multiplicative factors from the sum of certain sets of (finite-precision) real numbers?
Update based on Michael's answer (thanks again!) - Can the LLL or PSLQ algorithms provide a (knowably - i.e. not just incidental) unique solution for the set of integer multiplicative factors? Are ...
- 43
22
votes
3
answers
6k
views
Satisfiability of general Boolean formulas with at most two occurrences per variable
(If you know basics in theoretical computer science, you may skip immediately to the dark box below. I thought I would try to explain my question very carefully, to maximize the number of people that ...
- 4,729
3
votes
2
answers
889
views
computation, algebra, logic
So a really simple way of describing a digital computer is to say that it is a device for performing boolean operations. You feed it a bunch of bit strings, which is a description of the problem and ...
- 236k
15
votes
2
answers
3k
views
How to compute the rank of a matrix?
Okay, that's a misleading title. This is a somewhat subtler problem than undergraduate linear algebra, although I suspect there's still an easy answer. But I couldn't resist :D.
Here's the actual ...
- 2,416
8
votes
1
answer
794
views
Pseudorandom generators
Has there been any progress about constructing strong pseudorandom generators?
I'm not an expert on this topic, basically everything I know is a definition of a pseudorandom generator, the idea that ...
- 15.1k