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
2
votes
1
answer
227
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 ...
- 16.2k
1
vote
1
answer
288
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, ...
CommunityBot
- 1
4
votes
1
answer
449
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 : \...
- 53.3k
1
vote
0
answers
135
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 ...
- 11
0
votes
1
answer
235
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?
- 2,235
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 ...
- 599
3
votes
1
answer
540
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
1
answer
362
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 ...
- 3,475
1
vote
3
answers
501
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):
...
- 73.2k
2
votes
1
answer
2k
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 ...
- 123
3
votes
0
answers
299
views
Geometric/Analytic techniques for constructive and asymptotic bounds in the Lee metric
Slight extension of cross posting from
https://cstheory.stackexchange.com/questions/7408/lee-metric-gilbert-varshamov-and-hamming-bounds-for-larger-relative-distance-rang (closed there)
The ...
CommunityBot
- 1
1
vote
1
answer
283
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 ...
1
vote
0
answers
376
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 ...
CommunityBot
- 1
6
votes
1
answer
516
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 ...
- 1,951
0
votes
1
answer
182
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, ...
CommunityBot
- 1
2
votes
1
answer
435
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 ...
CommunityBot
- 1
3
votes
3
answers
390
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 ...
- 17.9k
3
votes
2
answers
255
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 ...
- 28k
2
votes
1
answer
653
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 ...
- 18.7k
2
votes
1
answer
2k
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,966
44
votes
3
answers
5k
views
"Simpler" statements equivalent to Con(PA) or Con(ZFC)?
Given any reasonable formal system F (e.g., Peano Arithmetic or ZFC), we all know that one can construct a Turing machine that runs forever iff F is consistent, by enumerating the theorems of F and ...
CommunityBot
- 1
0
votes
0
answers
270
views
Does there exist an algorithm for computing reachability in dynamic directed forests with fast update?
I'm interested in an algorithm which is able to compute reachability between any two nodes in polylog update (add or remove a valid edge) and query. I know that such an algorithm does exist for all ...
- 163
3
votes
0
answers
311
views
what is the largest gap between rank and approximate rank
$\epsilon$-approximation rank of a matrix $M$ is the minimum rank of a real matrix $A$ which differs from $M$ at most $\epsilon$ in each entry. Associating any function $f:X\times Y\rightarrow${1,-1} ...
- 363
2
votes
1
answer
995
views
final step(s) for a proof that a function is not primitive recursive
My function is $f:\mathbb{N} \rightarrow \mathbb{N},\ f(n)=2\uparrow ^n 3$ , the Ackermann(-Péter) function, with the second argument fixed to 3 (and "$\uparrow$" the Knuth up-arrow), which I believe ...
- 13k
5
votes
2
answers
629
views
Approximate search space on a 5x5x5 cube with 3 different possible classes?
Hey all,
I read the meta, and I realize this question might be pretty elementary for this site, but I'm having trouble computing this, and I know it won't take too much insight for someone to give me ...
- 153
5
votes
1
answer
523
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 ...
- 85.6k
5
votes
2
answers
680
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 2")...
- 17.9k
6
votes
2
answers
908
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 ...
CommunityBot
- 1
6
votes
3
answers
632
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 ...
CommunityBot
- 1
1
vote
1
answer
268
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 ...
CommunityBot
- 1
10
votes
5
answers
645
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 ...
CommunityBot
- 1
1
vote
2
answers
558
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 ...
- 3,622
1
vote
1
answer
311
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 ...
CommunityBot
- 1
4
votes
2
answers
2k
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 ...
- 27.5k
4
votes
2
answers
2k
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 dist....
- 4,462
8
votes
1
answer
2k
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 $p_{A\...
- 3,622
1
vote
2
answers
1k
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 ...
- 10.1k
4
votes
2
answers
2k
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$ colors,...
7
votes
1
answer
531
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 x.xx)\...
CommunityBot
- 1
3
votes
1
answer
507
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 ...
CommunityBot
- 1
7
votes
1
answer
767
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 ...
- 24.8k
24
votes
2
answers
3k
views
Counting subgraphs of bipartite graphs
I'm not a graph theorist or computational complexity specialist, so my apologies if this question is stupid or poorly posed!
Given a bipartite graph $G$ of $n$ vertices, how many induced subgraphs of ...
- 1,284
3
votes
0
answers
328
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 ...
- 513
8
votes
1
answer
2k
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 ...
- 4,014
2
votes
2
answers
2k
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,185
3
votes
2
answers
2k
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 ...
- 273
2
votes
1
answer
307
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 ...
- 577
1
vote
0
answers
576
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$ ...
- 1,839
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!
CommunityBot
- 1
6
votes
2
answers
1k
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 ...
- 17k