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
14
votes
1
answer
3k
views
Can Shor's Algorithm be modified to run efficiently on a classical computer?
Shor's algorithm is an algorithm which factors integers in polynomial time on a quantum computer. If one tries to run it on a classical computer, one runs into the problem that the state vector that ...
3
votes
1
answer
767
views
does recursive (decidable) languages closed under division (Quotient) with any language?
I need to prove or disprove that R languages are closed under divison.
I have managed to prove thet CFL are't closed under division. I read in wikipedia that RE languages are closed, but I didn't find ...
- 236k
17
votes
1
answer
2k
views
Is there an unambiguous CFL whose complement is not context-free?
I'm doing a little bit of research about context-free languages. A question that's popped up is whether or not there exists an unambiguous context-free language whose complement is not a context-free ...
- 4,713
6
votes
1
answer
194
views
Embedding Turing machine [closed]
I have some questions about Turing machines. Is there an embedding method where you embed Turing machines, finite automata into continuous space or graphs? Or are there geometrical approaches to ...
- 6,541
7
votes
3
answers
1k
views
Are there logical systems where formal proofs are not computer verifiable?
In a set-theoretic system using first-order logic, every proof could be written as a goal followed by a finite sequence of sentence where each one is justified by an axiom or previously established ...
- 1,127
12
votes
1
answer
749
views
Terminology: algebraic structure for "floating point" arithmetic
"floating point arithmetic" is a terminology that refer to the arithmetic perform over (finite) representation of real number. See the wikipedia article for more details.
In the formal specification ...
- 4,713
1
vote
0
answers
70
views
What is the value of a polynomial form for a data structure, aka a Container
Data structures like Lists and Trees are often referred to as Containers. They can be given as monads and containers are polynomial functors. The List monad is well known and can be given as a ...
- 1,313
3
votes
1
answer
120
views
Combinatorial problem about binary arrays with certain mutual distinctions
If there are m binary arrays (with 0 and 1) of length n, and between any two of these m arrays, there are k and only k same numbers (with the same site index in two different arrays). For example, if ...
CommunityBot
- 1
15
votes
1
answer
575
views
Constructive Mathematics and Termination
In the 1988 book The Universal Turing Machine A Half-Century Survey
there is the paper "The Confluence of Ideas in 1936" by Robin Gandy. In section 4.2, Gandy writes:
"If one accepts, on whatever ...
- 48.8k
2
votes
1
answer
69
views
Compute the hull of nonnegative linear combinations of a finite set, and the extreme points of the intersection of two polyhedra
Let $\mathbb{R}^d$ be $d$-dimensional Euclidean space
Let $\Delta=\{x\in\mathbb{R}^d_+:\sum_{i=1}^dx^i\leq1\}$ ($x^i$ is the i-th coordinate of $x$)
(Equivalently, $\Delta$ is the convex hull of $\{(0,...
- 151k
12
votes
2
answers
588
views
Ideal Membership without Certificate?
I have a homogeneous ideal $I=\langle f_1,\ldots,f_r\rangle$ of the polynomial ring $\mathbb C[X_1,\ldots,X_n]=:R$ where each of the $f_i$ is actually over $\mathbb Z$. My computations are usually ...
- 2,992
64
votes
1
answer
5k
views
How to be rigorous about combinatorial algorithms?
1. The question
This may be the worst question I've ever posed on MathOverflow: broad,
open-ended and likely to produce heat. Yet, I think any progress that will be
made here will be extremely useful ...
- 674
2
votes
0
answers
99
views
Recovering a rank-one matrix from its eigendecomposition after randomized rounding [closed]
Let $A = xy^T$ be a rank-$1$ matrix, and suppose every entry of $A$ is in $[0,1]$. We can create a binary matrix $A_{\rm rounded}$ by setting
$$ [A_{\rm rounded}]_{ij} = \begin{cases} 1 & \mbox{ ...
- 121
3
votes
1
answer
405
views
Is every complete bounded finite lattice equivalent to a sublattice of a powerset lattice?
More precisely, if I have a complete bounded finite lattice $C$, can I compute a lattice-operation-preserving map $C \to P(S)$? for some $S$. If not, is there another universal lattice structure that ...
- 156k
13
votes
2
answers
3k
views
Who first chose the names Alice and Bob for players A and B? [closed]
Who first chose the names Alice and Bob for the players (or observers) A and B?
CommunityBot
- 1
2
votes
0
answers
173
views
Transformation from the Bag monad to the List monad
The bag monad, sometimes called the multiset monad or free commutative monoid monad is a functor on Set that takes a set to its set of bags. These bags are like strings written in the elements of the ...
- 1,313
2
votes
1
answer
162
views
Is this cycling problem computable?
We have a group of $n$ people who must make a journey of length $d$. They are to start together, and their goal is to arrive at the destination at same time. They have a single bicycle, which they ...
- 543
6
votes
0
answers
1k
views
Hash functions and inner product
As part of a research project on derandomization of linear threshold functions I am working on, I am trying to understand the following problem:
Is there a small (polynomial rather than exponential)...
CommunityBot
- 1
6
votes
0
answers
176
views
Approximating a ray with an integer lattice point
Take $X$ uniform on the unit sphere in $\mathbb{R}^n.$ For $r>0$, take $S_r=\{x\in \mathbb{Z}^n: \sum_i x_i^2 \leq r^2\}.$
With $\|\cdot \|$ the 2-norm, what is the distribution (or at least the ...
27
votes
3
answers
2k
views
Expected edit distance
The edit or Levenshtein distance between two strings is the minimum number of single symbol insertions, deletions and substitutions to transform one string into another. For example $$\operatorname{...
3
votes
0
answers
405
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 ...
- 13k
3
votes
0
answers
264
views
Upward confluence in the interaction calculus
The lambda calculus is not upward confluent, counterexamples being known for a long time. Now, what about the interaction calculus? Specifically, I am looking for configurations $c_1$ and $c_2$ such ...
10
votes
0
answers
175
views
A combinatorial proof of the Harrow--Kolla--Schulman theorem
Let $Q^n := \{0,1\}^n$ be the Hamming cube with the Hamming metric. (Recall that the Hamming is defined by the distance $d(x,y) := \# \{ i : x_i \neq y_i \}$.
For integers $0 \leq k \leq n$, define a ...
- 679
1
vote
1
answer
341
views
How to create a quantum algorithm that produces 2 n-bit sequences with equal number of 1-bits?
I am interested in a quantum algorithm that has the following characteristics:
output = 2n bits OR 2 sets of n bits (e.g. 2 x 3 bits)
the number of 1-bits in the first set of n-bits must be equal to ...
CommunityBot
- 1
9
votes
1
answer
2k
views
graph signal processing
I have read this article
https://arxiv.org/abs/1307.5708
about vertix-frequency analysis on graph.
David IShuman
in this article claims that,"we generalize one of the most important signal ...
- 188k
1
vote
1
answer
69
views
Existence of dense graph with relatively small codegree?
Let $n$ be some parameter tending to infinity. I am wondering does there exists some kind of graphs $G$ on vertex-set $[n]$ with maximum degree less than $D$, so that
$D\ge n/w_1(n)$,
$e_G$, the ...
- 1,042
27
votes
3
answers
2k
views
Defining computable functions categorically
Computable functions may be defined in terms of Turing machines or recursive functions, or some other model of computation. We normally say that the choice doesn't matter, because all models of ...
- 3,029
23
votes
1
answer
1k
views
What, mathematically speaking, does it mean to say that the continuation monad can simulate all monads?
In various places it is stated that the continuation monad can simulate all monads in some sense (see for example http://lambda1.jimpryor.net/manipulating_trees_with_monads/))
In particular, in http://...
- 639
1
vote
1
answer
90
views
Probability of collision of sums of vectors multiplied by random matrix
Let $S$ and $T$ be sets of vectors from $\mathbb{R}^d$ such that $S$ and $T$ are at least different in one element.
Does there exist a random matrix $M \in \mathbb{R}^{d \times k}$, e.g., a gaussian ...
- 10.4k
2
votes
1
answer
70
views
For synchronizing eulerian finite state machines every proper subset of states has some larger state set leads to this subset
Suppose we have a deterministic complete finite automaton which is synchronized, meaning we have a reset word, i.e. a word which resets the automaton to a definite state, regardless from which state ...
- 38.6k
11
votes
1
answer
474
views
Representing field elements in a computer
I'm wondering if there is existing terminology to describe fields $F$ with the properties below. I don't have a completely precise description of the concept I have in mind, but hopefully this will be ...
- 4,727
2
votes
0
answers
76
views
First appearance of "structure tree"?
Let $G$ be a transitive permutation group acting on a set $\Omega$. A structure tree $T$ for $(G,\Omega)$ is defined as follows: if $G$ is primitive, then it consists of a root node connected by edges ...
- 20.2k
3
votes
1
answer
180
views
Non-trivial parity maps in graphs
(This question actually arose in real life when dealing with status bits with mutual influence.)
Let $G=(V,E)$ be a connected, simple, undirected graph with $|V| \geq 2$. For $v\in V$, let $N_G(v) = \...
- 6,051
7
votes
3
answers
2k
views
What is the right citation for the power iteration method to find eigenvalues?
What is the right citation for the power iteration method to find eigenvalues, if I want to cite the method in a paper? I've seen some Google PageRank references in this context. But Brin and Page ...
2
votes
0
answers
59
views
Maximum number of edges on $2^{k-1}+s$ vertices of a $k$-dimensional cube?
Let $k$ be an even number. For a $k$-dimensional cube (http://mathworld.wolfram.com/HypercubeGraph.html) $Q_k$, let $G$ be a subgraph of $Q_k$ with $2^{k-1}+s$ vertices, for $1\le s\le 2^{k-1}-1$. I ...
- 281
3
votes
0
answers
138
views
What are the axioms of the diagrammatic calculus for containers?
Ahman et al. wrote about when a container is a comonad. Containers can also be monads, such as List. This means that we can take all containers that are endofunctors on Set and they live in the ...
- 1,313
2
votes
1
answer
512
views
What is the (Co)Monad for a Bag
A Bag is a data structure, like a list, that stores items with no concept of order. The only operations on the structure is to add an item and then iterate through the items with no guarantee as to ...
- 1,289
15
votes
8
answers
3k
views
How Does Random Noise Typically Look?
How does random noise in the digital world typically look?
Suppose you have a memory of n bits, and suppose that a "random noise" hits the memory in such a way that the probability of each bit being ...
- 1,228
6
votes
1
answer
216
views
A "dense" extension of the set of primitive recursive functions
Let $\mathcal{PR}$ be the set of primitive recursive functions. Let $\mathcal{PR}(f)$ be $\mathcal{PR}$ which we have amplified by adding (a recursive) $f$ the in the set of initial functions. To make ...
- 236k
3
votes
2
answers
830
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 ...
- 2,993
6
votes
1
answer
1k
views
Is there any "fundamental" distinction between min-plus, max-plus, min-product, and max-product algebras?
In the paper Faster Algorithms for Max-Product Message Passing by McAuley and Caetano (see e.g. here or here), several statements are made which seem mathematically questionable to me.
For ...
- 118k
4
votes
2
answers
591
views
Connection between countable ordinals and Turing degrees
$\omega^{CK}_1$ is the supremum of all the recursive ordinals, where an ordinal $\alpha$ is recursive if there is a computable ordering of a subset of the naturals with order type $\alpha$.
For a ...
- 4,201
3
votes
0
answers
240
views
Applications of logic in theoretical and practical Computer Science [closed]
Can anyone suggest theoretical and/or practical applications of logic (modal, dynamic, Lukasiewici etc.) in Computer Science (like Markov Chains for linear algebra), as well as some open-source books ...
- 139
1
vote
0
answers
63
views
Congruency check for set of points in 3D using inertia tensor
You're given two set of points $A, B\subset \mathbb R^3:|A|=|B|=n$. You have to check if those sets are congruent, i.e. there exist some mapping $\sigma : A \to B$ and combination of translation and ...
- 1,171
7
votes
1
answer
453
views
What Turing degree would allow you to "compute" the axioms of ZFC in some countable model of ZFC?
It is established in this post that you there is no computable model of ZFC, yet it can be computed in by a PA-degree oracle machine. Note that when we see "compute a model", we just mean that ...
- 39.8k
2
votes
2
answers
169
views
Decidability of matrix problem in ${\mathbb Z}/p{\mathbb Z}$
Let $p$ be a prime number, $n$ be a positive integer, and let ${\mathbb Z}_p^{n\times n}$ denote the set of $n\times n$-matrices over ${\mathbb Z}/p{\mathbb Z}$.
Suppose we are given an integer $m>...
- 63.9k
1
vote
2
answers
79
views
Is there a feasible way to compute the number of steps between two sequences generated by a linear feedback-shift register?
Consider a full-period LSFR with a feedback polynomial of degree n. In the cyclic sequence generated by the LSFR, each n-bit sequence appears exactly once. Given two n-bit sequences, one can define ...
- 10.4k
5
votes
0
answers
307
views
Quantum P vs NP equivalent problem
If $P = NP$, does it follow that $BQP = NP^{BQP}$?
I came up with this question when I was thinking about how $P = NP$ can be described as "does every decision problem where a proof for YES can be ...
- 5,407
19
votes
3
answers
1k
views
Can you consistently add axioms about the Busy Beaver function to ZF?
Consider a Turing Machine with $N$ states which checks all theorems of ZF and halts upon finding a contradiction. If ZF were consistent and could prove the value of $BusyBeaver(N)$, then it would be ...
- 870
6
votes
1
answer
458
views
Applications of small Kakeya sets over finite fields
It was proved by Dvir that a Kakeya set in $\mathbb{F}_q^n$ has size at least $q^n/n!$, a bound which was later improved to $q^n/2^n$.
For $n = 2$ and $q$ odd the exact bound is $q(q+1)/2 + (q-1)/2$ ...
- 223