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
3
answers
415
views
Efficiency of representations of number
In everyday practice the most common ways to represent integers are the binary and decimal systems. We use floating point or fixed point systems to (approximately) represent the reals. There are some ...
- 30.1k
10
votes
2
answers
611
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....
- 13.6k
1
vote
0
answers
265
views
What does homomorphism between languages mean to the correspoding Turing Machines?
According to the article: every c.e.language over $\Sigma^*$can be formed by homomorphism from a Dyck language over $\Sigma^{'}$ intersection with a minimal linear language over $\Sigma^{'}$ to the ...
- 3,094
5
votes
1
answer
277
views
Program analysis for Turing machines
What is considered the state-of-the-art on program analysis (static and dynamic) for Turing machines? What references can I consult for this problem?
I am thinking of things like determining whether ...
- 151k
1
vote
1
answer
347
views
Finding a subgraph of cliques with the minimum total sum weight
Consider the following graph problem. For a number $K$ and a set $\mathcal{K} = \{ 1, \ldots,K\}$, we have a set of vertices $V_k^s$ for all $s \subset \mathcal{K} \setminus \{k\}$, $s$ is not empty ...
- 113
4
votes
1
answer
588
views
Another conjecture on sum $A+B=C$
Could You give your ideas, your comment, or a referen for a conjecture as follows:
Consider $A, B, C$ be three positive integers numbers. By Fundamental theorem of arithmetic we write:
$A=a_1^{x_1}...
- 477
4
votes
1
answer
248
views
Game theoretic aspects of Wang tiles?
Wang tiles are interesting in that they can simulate Turing machines. My question is whether anyone has studied their game theoretic properties?
In particular, we could imagine a game in which you ...
CommunityBot
- 1
5
votes
1
answer
1k
views
Generalizing Big O notation to arbitrary vector spaces
I'm constructing a Coq library for Big-O notation. Naturally, I'd like it to be as general as possible. The Wikipedia page on Big-O notation says
The generalization to functions taking values in ...
- 47.3k
7
votes
1
answer
258
views
Oracle queries asked in parallel
Definition: Assume that $\phi(q)$ is of the form $\exists y \leq 2^{p(n)} \varphi(q,y)$, where $p$ is a polynomial and $n = |q|$ (i.e. $n$ is the length of the binary representation of $q$). Then a ...
- 47.3k
18
votes
3
answers
2k
views
How do we express measurable spaces using type theory?
A measurable space $(X,\mathcal X)$ consists of a set $X$ equipped with a $\sigma$-algebra of subsets $\mathcal X$. I would like to write computer programs involving measurable spaces, but to the best ...
CommunityBot
- 1
1
vote
1
answer
187
views
Random iteration of a set of monotone maps until fixed point
Let $P$ be a poset with a least element $\bot$ ($\forall x \in P.\ \bot \le x$).
Let $M$ be a set of monotone maps $P \to P$.
Call $x \in P$ reachable if $x = f_1(f_2(...f_n(\bot)...))$ for some ...
- 36
46
votes
7
answers
13k
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 ...
CommunityBot
- 1
9
votes
1
answer
154
views
Inductive and reducible functions
The question was asked by a Computer Scientist and is closely related to parallel computing. But it is clearly of algebraic nature, so I decided to post it here.
Let $X$ be a set and $\bar X$ be the ...
- 23.7k
6
votes
1
answer
304
views
Shortest vector problem over polynomials
In shortest vector problem, given a lattice in $\Bbb Z^n$, we seek the shortest non-zero vector in the lattice. This problem is computationally difficult.
Answer in Evidence for integer factorization ...
- 13.9k
2
votes
0
answers
323
views
Is there standard notation for restriction partial functions?
Given a partial function $f : A \rightarrow B$, and a subset $S \subseteq A$, we get a new partial function $$f \restriction_S : A \rightarrow B$$ by restriction. However, I prefer to analyse $f \...
- 20.9k
4
votes
3
answers
260
views
An inequality concerning formulas and Boolean functions
We define $S(\phi)$ of formula $\phi$ to be the number of computational gates in a minimal $\{\neg, \wedge, \vee\}$-formula computing $\phi$.
Conjecture. If $\phi_1(a_{11}, \dots, a_{1y_1})$, $\dots$,...
- 6,694
1
vote
1
answer
575
views
Decomposing a sphere (or defomed sphere) into a vertex-transitive graph with fixed-length curved edges
Please see the original problem specification (which Joseph O'Rourke was responding to in his answer) below.
Motivation -
I'm interested in a particular case of the problem where one wants to ...
- 151k
2
votes
0
answers
49
views
Bounding the number of identical rows in a Boolean matrix using summary statistics
I am currently stuck on the following problem: given a $n \times d$ Boolean matrix $X = [x_1,\ldots,x_d]$ where each $x_j =[x_{1,j},\ldots,x_{n,j}]^\top \in \{0,1\}^n$, I want to bound the number of ...
- 379
3
votes
2
answers
517
views
Threading pinholes in the wall of cylinder to pass through an internal coordinate
Imagine I take a sheet of paper and use a pin to generate an $N$x$M$ rectangular array of small holes. I then fold the sheet to form a cylinder of radius $r_c$ and height $h_c$, where there are $N$ ...
CommunityBot
- 1
4
votes
0
answers
140
views
Is there any accepted single-word that means "partial function"?
When I'm explaining things involving partial functions, I usually end up stumbling over my words, like so: "Suppose $f : A \rightarrow B$ is a function, uhh, sorry I mean a partial function, and ...
- 3,793
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 ...
3
votes
2
answers
316
views
Should we expect there to be a problem that is PH-hard but not PSPACE-hard?
That is, is there a problem that all problems in the polynomial hierarchy can be reduced to in polynomial time, but which some PSPACE problem cannot be reduced to in polynomial time? Clearly if the ...
CommunityBot
- 1
13
votes
1
answer
597
views
Does Langton's ant cover every n by 6 gridded torus?
This post follows this other post about times cover by Langton's ant of $n$ by $n$ gridded torus.
For $n$ by $n$ gridded torus, I've checked for $n \le 1000$ that the ant covers all. This fact needs ...
CommunityBot
- 1
66
votes
4
answers
11k
views
What are the implications of the new quasi-polynomial time solution for the Graph Isomorphism problem?
This week, news came out that Laszlo Babai has found a quasi-polynomial time algorithm to solve the Graph Isomorphism problem (that is: $O(\exp(polylog(n)))$). He is giving a series of talks this week,...
CommunityBot
- 1
6
votes
2
answers
251
views
Are there recursive sets $X$ with Property A that contain infinitely many incompressible strings?
Let us say a set $X$ satisfies Property A if$$\liminf_{n \to \infty} {{\left|X^{\le n}\right|}\over n} = 0.$$Are there recursive sets $X$ satisfying Property A that contain infinitely many ...
- 678
2
votes
0
answers
113
views
Description of all total recursive functions where operator is effective?
What is a description of all total recursive functions $g(x)$ for which the operator$$\Phi_g: \mathcal{F}_2 \to \mathcal{F}_1$$defined by the formula$$\Phi_g(f)(x) := g(\mu y(f(x, y) = 0))$$is ...
- 45
5
votes
0
answers
163
views
A Combinatorial Problem on Extremal Set Theory
Given a ground set $[n]$, under what condition of parameters $a,b,c$ does a family of subsets $\mathcal{F}\subseteq 2^{[n]}$ with the following property exist?
(i) $\forall S\in \mathcal{F}$, $|S|=a$....
- 37.7k
2
votes
3
answers
9k
views
How can I combine my interests for pure mathematics and computer science in college? [closed]
I’m a high school senior who's gone through quite the self-introspection the past few months while applying for college, and I have a bit of a dilemma. All my life, I've loved & excelled at ...
- 169
5
votes
2
answers
4k
views
Is there any math foundation for map/reduce? [closed]
For a while I was thinking that you just need a map to a monoid, and then reduce would do reduction according to monoid's multiplication.
First, this is not exactly how monoids work, and second, this ...
- 562
-3
votes
3
answers
338
views
Can we decide whenever a function is the derivate of another function in this Language?
Our EXP functions are made in the following way:
Any constant $ \in \Bbb R$ is a EXP
$X \in \Bbb R$ is a EXP
$sin( g(x))$, $cos( g(x))$ are in EXP if $g(x)$ is a EXP
$tan( g(x))$ is a EXP if $g(x)$...
CommunityBot
- 1
7
votes
2
answers
599
views
Is there a noncomputable set which can be described by a probabilistic Turing machine with bounded error?
Does there exist any noncomputable set $A$ and probabilistic Turing machine $M$ such that $\forall n\in A$ $M(n)$ halts and outputs $1$ with probability at least $2/3$, and $\forall n\in\mathbb{N}\...
- 1
7
votes
3
answers
3k
views
Is there an algorithm that can "reverse engineer" a Regular Expression?
Given a Regular language (represented as a black box to which one can apply inputs and get 0/1) Is there an algorithm that can find a finite deterministic automaton that produces that language?
3
votes
1
answer
158
views
Matroids of hypercubes
Let $M_k$ be the (oriented) matroid of the $2^k$ points $B_k = \{-1, 1\}^k$ in $\mathbb R^k$. In other words, the (oriented) circuits of $M_k$ are the minimal (signed) linear dependences among $B_k$.
...
- 984
5
votes
1
answer
178
views
Degree $d$ function with boolean inputs with small range is a junta?
Let $f : \{-1,1\}^n \rightarrow \{-1,1\}$ be a boolean function which is of degree at most $d$ when expressed as a multilinear polynomial ($f(x) = \sum_S \hat{f}(S) \prod_{i \in S} x_i$). It is known ...
- 6,694
1
vote
3
answers
1k
views
best deterministic complexity for factoring polynomials over finite field
I would like to know currently what's the best deterministic complexity for factoring polynomials over finite field (without the assumption of GRH)? I have searched on google, there are many source, ...
- 537
4
votes
1
answer
434
views
Giving the same concept different names in the same paper
I found a seminal paper of renowned authors (Inference of Finite Automata Using Homing Sequences (1993) by Ron Rivest and Robert Schapire) in which the authors define the very same set-theoretic ...
- 4,529
4
votes
0
answers
155
views
Effective "almost enumeration" of monotone boolean functions
Denote by $\mathcal{M}(n)$ the set of all monotone functions $\{0,1\}^n \to \{0,1\}$.
Can $\mathcal{M}(n)$ be represented as $\mathcal{M}(n) = \{ f(t) | t\in \{0,1\}^k \}$ such that:
1) $k = \log |\...
CommunityBot
- 1
1
vote
0
answers
237
views
Continuation of strictly monotone function in $R^n$
Let $f(x_1,...,x_n)$ be $C^0$ continuous function $R^n\to R$ defined on a compact domain $A\subset R^n$. Let $f$ be strictly monotonously increasing w.r.t. every argument in the domain of definition. ...
CommunityBot
- 1
4
votes
2
answers
155
views
Are there complexity classes X weaker than the linear time hierarchy such that any r.e. set is a coordinate projection of a set in X?
If $A\subseteq\mathbb{N}$ is recursively enumerable, then there is a $\Delta^0_0$ set $B\subseteq\mathbb{N}^2$ such that $A=\{x|\exists y\;(x,y)\in B\}$. $\Delta^0_0$ consists of exactly the sets in ...
- 47.3k
7
votes
3
answers
1k
views
How slow are direct solutions of NP-complete problems on computers?
Sometimes I see that people call a problem NP-hard and because of that refuse to create computer algorithms that directly solve it. I think I've never read actual benchmark results for such problems. ...
- 151k
0
votes
2
answers
487
views
Cannot understand the functor from Set to List
I'm reading a few books on category theory, and they talk about a functor from Set to List, with a object s in Set mapped to a list of elements of s. However, there are many lists possible from s, ...
CommunityBot
- 1
2
votes
0
answers
328
views
The category of sets and "stateful" functions
In some programming languages, there's functions whose output can change on the basis of changing internal state; for example, the second time you compute $f(5)$ you might get a different answer. This ...
CommunityBot
- 1
10
votes
1
answer
710
views
Profunctorial Grothendieck Construction?
I've been taking the ideas expressed in "Functors are Type Refinement Systems" seriously lately and it's lead me to a form of the Grothendieck construction I've never seen before.
The idea in that ...
- 66.8k
1
vote
2
answers
345
views
Coding SLEs (Schramm–Loewner Evolution) eg. SLE(6)
Any references/links on codes for SLEs written in C++ or Matlab that I can run in Windows (visual studio)?
The only code I found was:http://math.arizona.edu/~tgk/research.html but the link was empty. ...
- 1,791
1
vote
1
answer
442
views
A morphism-revealing category? [closed]
Categories of sets and functions can be considered as subcategories of Set but when considered as subcategories of the category SubSet, of pairs of sets with pairs $(X,S)$, $S\subseteq X$, as objects ...
- 862
2
votes
1
answer
150
views
Probability of collision of some family of hash functions
Given $x$ and $y$ in $\mathbb{R}$, and let $\mathcal{H} = \{ h \mid \mathbb{R} \to \mathbb{N} \}$ be a family of hash functions where $ h(x) = \left\lfloor x + \sum^C_{i=1} U_i \right\rfloor$ for some ...
- 128k
4
votes
1
answer
401
views
What do we call this quantifier ("binder")?
There's a quantifier ("binder", whatever), call it $\alpha$, defined as follows: $\alpha x.\tau$ is the (usually infinite) expression obtained by applying the substitution $\{x \mapsto \tau\}$ to the ...
- 48.8k
15
votes
1
answer
748
views
Digital physics and "Gandy-like" machines
Various physicists, famously John Wheeler, have asserted that physical information is the central object of study in physics, in the sense that an object or concept is "physically meaningful" if it ...
- 188k
0
votes
0
answers
139
views
Reconstructing a graph from set of sequences of edges
I have the following problem to solve: Given a set of sequences of edges of an undirected, planar, connected graph, find a "reasonable" reconstruction of the graph. There is an unknown number of ...
- 283
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.
...
CommunityBot
- 1