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
1
vote
1
answer
244
views
How many edges can you put in a graph such that every edge belongs to a minimal $k$-cycle?
I am trying to solve:
Given $n, k$, find maximum $m$ such that there exists a graph on $n$ nodes, $m$ edges such that every edge is part of a minimal $k$-cycle.
I only care about the asymptotic ...
CommunityBot
- 1
4
votes
1
answer
155
views
Self-similarity in the theory of computability
Let $M = w_0w_1... \in \{0,1\}^*$.
For any computable function $f$ define $M_f = w_{f(0)}w_{f(1)}...$
Let for any computable strictly increasing function $f$ there is continuous
computable mapping ...
- 24.8k
2
votes
0
answers
63
views
Private Randomness extractor
Suppose we are given two random variables $X$ and $Y$ with fixed marginal and joint distribution. What is the maximum randomness that we can extract from $Y$ that is independent from $X$, that is, if $...
- 1,109
4
votes
1
answer
442
views
Fundamental Problems in Mathematics that, without Computer Sciences, would not be resolved? [closed]
Could you please give examples of fundamental questions in mathematics (let us say, pure mathematics) which were resolved fundamentally by the use of computers? More precisely, are there examples that ...
- 26.3k
6
votes
1
answer
135
views
Generalising the adherence operator and its closure properties with regard to regular (rational) languages
Let $X$ be an alphabet and denote by $X^{\omega}$ the set of all infinite sequences (i.e. words) in $X$. A subset $L \subseteq X^{\omega}$ is called $\omega$-regular if it is acceptable by some Büchi-...
- 841
5
votes
1
answer
327
views
Subsets of all Diophantine's sets
I have asked this question on math.stackexchange already:
https://math.stackexchange.com/questions/627461/subsets-of-all-diophantines-sets
Function $\mathbb{N}^k \to \mathbb{N}^m$ is computable $\...
CommunityBot
- 1
27
votes
10
answers
4k
views
Can We Decide Whether Small Computer Programs Halt?
The undecidability of the halting problem states that there is no general procedure for deciding whether an arbitrary sufficiently complex computer program will halt or not.
Are there some large $n$ ...
CommunityBot
- 1
30
votes
4
answers
2k
views
A programming language that can only create algorithms with polynomial runtime?
Has someone constructed a programming language that can construct all the algorithms in P, and no others?
I'm interested in this restriction coming from the syntax naturally, as opposed to just being ...
CommunityBot
- 1
4
votes
0
answers
568
views
About "natural proof" of Razborov and Rudich
The famous "Natural Proof" paper ,http://www.cs.umd.edu/~gasarch/BLOGPAPERS/natural.pdf , of Razborov and Rudich gives a barrier for any proof that try to separate P and NP. It mainly shows that if ...
- 781
3
votes
2
answers
1k
views
Place N points in a 3d cube in a way that maximizes the minimum of their pairwise distances
Place $N$ points in a 3d cube in a way that maximizes the minimum of their pairwise distances.
The problem can easily be solved for $N\lt5$, but how to proceed for larger $N$?
- 7,276
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 ...
- 2,205
10
votes
2
answers
3k
views
How difficult will it be for me to switch fields (details below) after my Ph.D. in pure mathematics?
I'm a first year postdoctoral researcher, working in pure areas of Riemann surfaces and differential geometry, after just finishing my Ph.D. in 2013. Recently I've also started taking interest in ...
5
votes
1
answer
346
views
What prefix and factors determine a ultimately periodic word uniquely
Let $\xi$ be an ultimately periodic sequence, i.e. there exists finite sequences $p, q \in X^*$ such that $\xi = pq^{\omega}$. Does there exists a $n > 0$ such that the prefix of length $n$ and all ...
- 38.6k
0
votes
0
answers
154
views
Proof of conjecture that permutation-free automata restrict the possible states visitable from a stringset sharing prefixes and infixes
An automaton $\mathcal A = (X, Q, \delta, q_0)$ is called permutation-free iff no word $w \in X^*$ induces a nontrivial permutation of a subset of the states of $\mathcal A$. More formally for any $R \...
- 798
8
votes
2
answers
567
views
Where should I learn about Kolmogorov complexity of overlapping substrings?
I would like to know more about the relationship between the Kolmogorov complexity of a string and that of its substrings. The relation that up to an additive constant, $K(x,y) = K(x) + K(y\ |\ x, K(...
- 236k
5
votes
1
answer
362
views
Drawing graphs on circles
Please consider the following problem:
Given: a simple graph (without self-loops and without multiple edges) $G$ on $n$ vertices.
Task: place equidistantly the vertices of $G$ on a circle of unit ...
- 3,004
12
votes
1
answer
4k
views
How to check whether a positive integer can be written as linear combination of given others, where all coefficients are positive?
Let $n$, $k$ and $m_1, \dots, m_k$ be positive integers. Which is the most efficient
algorithm to find out whether there are positive integers $a_1, \dots, a_k$ such that
$n = \sum_{i=1}^k a_i m_i$?
...
- 24.7k
5
votes
3
answers
794
views
Are paths in HoTT perhaps just "cost-free" paths?
Homotopy type theory (HoTT) doesn't seem to say anything about "mutations" of values in type $T$, an important concept in computer science. Mutations occur when you "change a value" of some variable $...
- 3,393
1
vote
1
answer
169
views
Interaction-based approximation for HP-complete λ-theory?
We are looking for a proof or counter-examples for the following hypothesis.
Two combinators $M$ and $N$ are solvable and equivalent in the HP-complete sensible $\lambda$-theory iff either
$$
\exists ...
1
vote
1
answer
223
views
Hypothesis: interaction-based model for λKβη
We are looking for a proof or counter-examples to the following
Hypothesis. In interaction calculus $\langle \varnothing\ |\ \Gamma(M, x) \cup \Gamma(N, x)\rangle \downarrow \langle \varnothing\ |\ ...
11
votes
1
answer
4k
views
How much does a quantum oracle to find a needle in a haystack really cost?
Among the basic algorithms of quantum computations Lov Grover's result on quantum search stands out, both in regards to its intrinsic interest, and for its undisputable elegance.
Grover's algorithm ...
- 7,800
4
votes
1
answer
172
views
Subsets of $\omega$-regular lanuages accepted by automata with special acceptance condition
Let $\mathcal A = (X, Q, \delta, q_0, F)$ be a deterministic finite automata with the following acceptance condition on infinite words:
The automata accepts $\xi \in X^{\omega}$ with respect to $F$ ...
- 236k
4
votes
3
answers
460
views
Existential quantification over regular predicates
A regular language over an alphabet $\Sigma$ is a subset of the set of all words over $\Sigma$ that can be accepted by some finite automaton. A regular language identifies a certain property of ...
CommunityBot
- 1
9
votes
1
answer
960
views
Categorical Semantics for Second-Order Logics
I am currently doing some work using a categorical semantics of first-order logic. The specific semantics I am using is due to Andrew Pitts, as described in:
Categorical Logic, Andrew M. Pitts, ...
- 356
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
...
CommunityBot
- 1
13
votes
1
answer
799
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 ...
- 3,692
6
votes
0
answers
291
views
Modelling the difficulty of mental calculation. [closed]
Are you aware of any work that tries to model the difficulty of evaluating a formula mentally (for your average, numerate, person, not a trained mental calculator)?
For instance, evaluating an ...
CommunityBot
- 1
6
votes
6
answers
402
views
Physical Disturbances to Computations [closed]
In this paper, page 7 (160 of the Journal), Fig 3, there is a particularly amusing (not to the authors!) caption:
"... On April 1 of year 2 in the $S_0$ experiment, the computer was hit by a cosmic ...
CommunityBot
- 1
1
vote
1
answer
1k
views
Proof of the lower bounds of time of algorithm working [closed]
I have asked this question on math.stackexchange already: https://math.stackexchange.com/questions/515920/lower-bounds-on-the-running-time
There are some problems, when there is non-trivial lower ...
CommunityBot
- 1
5
votes
2
answers
450
views
A simple language and systematic computations
The following somewhat popular simple computer language was enjoyed on sci.math, sci.math.research, pl.sci.matematyka, and perhaps before and after at several places (I wish I knew it's exact history)....
- 851
20
votes
4
answers
2k
views
Kolmogorov complexity is the strongest noncomputable function
Yury I. Manin says that Kolmogorov complexity (in some nontrivial sense) is the strongest noncomputable function ("Колмогоровская сложность... невычислима... она во многих интересных смыслах ...
CommunityBot
- 1
2
votes
0
answers
106
views
Is there any track for proving $D=NP$, besides showing that $D$ has polynomial-bounded universal quantifiers?
Background
By the MRDP theorem, every for every recursively enumerable set $S$, there exists a Diophantine polynomial $p$ such that
$$x \in S \iff \exists y_1, \dots, y_n \in \mathbb{N} \text{ such ...
- 1,389
2
votes
1
answer
224
views
Parsing of Stochastic Contex-Free Grammars (SCFGs)
I am interested in parsing of general SCFGs.
I am aware of the Earley parser for the general CFGs. The only general algorithm for parsing SCFGs that I am aware of is the Earley-Stolcke parser : http:/...
CommunityBot
- 1
5
votes
1
answer
700
views
What is the pathwidth of the 3D-grid (mesh or lattice) with sidelength k?
This question is now also on https://cstheory.stackexchange.com/questions/4081/what-is-the-pathwidth-of-the-3d-grid-mesh-or-lattice-with-sidelength-k, where a discussion started, and one reference ...
CommunityBot
- 1
1
vote
0
answers
157
views
Indecomposability of image transformations (pure algebra). Open questions
W-transformations -- definitions
We will consider a class called finite window transformations $\ T:C^\mathbb Z\rightarrow C^\mathbb Z\ $ defined a paragraph below; $\ \mathbb Z\ $ is the ring of ...
- 7,500
1
vote
0
answers
206
views
Testing functional equivalence
We are looking for the most efficient (most recent, or best) techniques to check if two algebraic expressions (elementary, Calculus-type functions) are equivalent (or if an expression is equivalent to ...
- 6,210
4
votes
0
answers
209
views
Rough structure of the double coset space/Graph bijections up to automorphisms
I am dealing with bijective maps $\pi:\Gamma_1\to \Gamma_2$ between two graphs with the same number of vertices $N=O(10)$.
The graphs have a significant automorphism group (these are disconnected ...
- 679
8
votes
1
answer
585
views
Main problems on lattice-basis reduction algorithms (such as LLL)?
What are the main open problems on lattice-basis reduction algorithms (such as LLL)? I am looking for problems satisfying the following two conditions:
(a) their solution would likely be of some ...
- 19k
1
vote
3
answers
694
views
unbounded complexity
If a language L is decidable, does that imply that the is a computable function f such that L is in O(f(n)) ?
For example what would be the complexity class of the language of "provably halting ...
- 44.4k
4
votes
0
answers
233
views
Question about constructing an admissible ideal of a quiver of an algebra with the aid of a computer
Let $k$ be an algebraically closed field and $A$ a finite-dimensional, basic, connected $k$-algebra. Then $A$ is Morita-equivalent to a quotient of a path algebra $kQ/I$ and $I$ is an admissible ...
- 1,755
3
votes
1
answer
1k
views
Collatz conjecture— finite state machine transducer construction, origination?
wikipedia has an entry on the Collatz conjecture with a section on As an abstract machine that computes in base two. this apparently describes a construction of a FSM transducer computing sequential ...
CommunityBot
- 1
7
votes
1
answer
548
views
Constructing Metrics for specific Topological Spaces, and Refinements of the Cantor-Space in particular
I have a Problem in general, given some some Topological Space $(X, \tau)$ from which I know it is metrisable, how can I find a metric (that is at best in some sence constructive and easy, at the very ...
- 44.4k
11
votes
1
answer
949
views
Magma "actions" (or alternatively, "What is the Yoneda lemma for magmas?")
Arguably the most import thing about groups, semigroups and more generally categories, is that they can act on sets (or even collections of sets in the case of a category). This is the basis for all ...
- 32.5k
1
vote
1
answer
324
views
Problem to a solution
Consider an NP hard problem $\frak P$ which takes an input of length n
$\frak P$ can be solved partially by a factor $ p_i = p(n,i)\in$ [0,1)... by a polynomial time algorithm $\mathcal A(i)$ ...
CommunityBot
- 1
15
votes
2
answers
4k
views
Switching from pure mathematics (e.g. geometry) to more applied areas (e.g imaging) after Ph.D., as postdoc and chance of getting such a postdoc?
Before I start my question, I should probably mention that this question might not be the right question to ask here, but I tried academiabeta, and stackoverflow, but without getting any to-the-point ...
- 9,627
4
votes
0
answers
73
views
Is the $d$-dimensional Arrangement of Trees still $NP$-hard?
The $d$-dimensional Arrangement Problem for general graphs is known to be $NP$-hard since the special case $d=1$ (OLA) already is (Garey et al, [1976]). For Trees however, the one dimensional case can ...
- 41
3
votes
1
answer
296
views
Question about the elementary divisors of a special matrix
I have the following question:
Is there a closed formula for the elementary divisors of the Matrix
$M=\lbrace (m_{ij})\rbrace_{i=1,...,n,\ j=1,...,k}$, where $m_{ij}$ is the greatest common ...
- 25.3k
0
votes
0
answers
347
views
An interesting version of the problem “balls into bins”
Consider n people, each has k identical balls. Each people choose k different bins from m bins, constrained by the condition that there are no two people choose exactly the same k bins. For instance, ...
- 1
17
votes
0
answers
449
views
Splay trees and Thompson's group $F$
( I apologize for only indicating some easy to find references, but new users are not allowed to link more than five). This is very speculative, but:
Question: Is there a reformulation of the Dynamic ...
- 18.7k
1
vote
0
answers
111
views
Schönhage's SMM with only one instruction
It is possible to implement $\lambda$-calculus in Schönhage's storage modification machine using an infinite set of nodes and one single program consisted exclusively of (about hundred) instructions ...