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
2
answers
482
views
Satisfiability problem for FOL[<,R]
Let FOL[<,R] be the fragment of first-order logic enriched with two relational symbols < and R and the first-order axioms that say:
< is a strict partial order and R is an irreflexive and ...
- 236k
58
votes
10
answers
10k
views
A clear map of mathematical approaches to Artificial Intelligence
I have recently become interested in Machine Learning and AI as a student of theoretical physics and mathematics, and have gone through some of the recommended resources dealing with statistical ...
- 835
6
votes
1
answer
365
views
Large subgroups of Knuth's non-associative "group" on ${\cal P}(\mathbb{N})$
Donald Knuth introduced a fast, bit-wise approximation to integer addition by $$(a,b) \mapsto a \, ^{\land} \, b \, ^{\land} \, ((a \text{ & } b) \ll 1)$$
where $a,b$ are given in binary and $\,^{\...
- 13.4k
6
votes
2
answers
769
views
Representation of μ-recursive functions
Can every μ-recursive function be defined using a single instance of the μ operator applied to a primitive recursive function?
According to Wikipedia, any μ-recursive function can be expressed as the ...
- 1,446
17
votes
6
answers
6k
views
Revisiting the unreasonable effectiveness of mathematics
Question:
On balance, with theoretical advances in algorithmic information theory and Quantum Computation it appears that the remarkable effectiveness of mathematics in the natural sciences is quite ...
- 19.6k
4
votes
2
answers
320
views
Approximating a fraction with a given denominator
Let $M$, $N$ be large natural numbers (say ~200 bits). Let $L$ be a smaller number, (say ~100 bits).
I want to approximate the fraction:
$$\frac{M}{N} \sim \frac{k}{L+r}$$
where $r$ is at most $L$. In ...
- 12.3k
2
votes
0
answers
111
views
Constructing Hamiltonian circuits in acyclic digraphs
Any directed graph $G$ lacking cycles can acquire a Hamiltonian circuit through the addition of a sufficient number of edges.
Q. Is there a method to minimize the addition of edges to achieve a ...
- 63.9k
2
votes
1
answer
60
views
Left-shift cycle generating maps $f:\{0,1\}^{c_0}\to\{0,1\}$ for fixed length $c_0$
This is a strengthening of an older question.
Is there a positive integer $c_0$ with the following property?
For every integer $n\geq c_0$ there is a function $f:\{0,1\}^{c_0}\to\{0,1\}$ such that ...
- 23.7k
36
votes
8
answers
3k
views
Examples of errors in computational combinatorics results
I would like to collect examples of errors in published numerical results in computational combinatorics: where a result (typically a counting of some objects, or an extremal quantity within some ...
- 1,446
16
votes
2
answers
3k
views
Why is there no product type in simply typed lambda-calculus?
$\DeclareMathOperator\Pair{Pair}\DeclareMathOperator\First{First}\DeclareMathOperator\Second{Second}\DeclareMathOperator\Left{Left}\DeclareMathOperator\Right{Right}\DeclareMathOperator\Choice{Choice}$...
- 12.9k
22
votes
9
answers
17k
views
Fast evaluation of polynomials
Hello everybody !
I was reading a book on geometry which taught me that one could compute the volume of a simplex through the determinant of a matrix, and I thought (I'm becoming a worse computer ...
43
votes
4
answers
5k
views
Lists as a foundation of mathematics
I am wondering if there is a foundation of mathematics where not sets or "set-like objects" (such as objects of a suitable topos as in ETCS) are the primitive notion, but rather lists. These ...
- 4,359
1
vote
0
answers
116
views
Sudden drop in complexity class due to the more general correlations
Recently I was asking about the impact of the groundbreaking result MIP*=RE on logic and proof theory (see this discussion). Surprising as it is I got confused with the following: MIP* is a ,,quantum''...
- 9,330
5
votes
2
answers
1k
views
Definition of continuous functions in order theory
If we have a complete partial order (i.e. directed complete) I find frequently the following definition of a continuous function. A function $f:A\to B$ where $A$ and $B$ are cpos is called continuous ...
- 1,446
0
votes
0
answers
60
views
Given a set of time-series data, how would I determine another time-series is a linear combination of the set?
In other words, determine if sum linear combination of existing time-series could result in the desired time-series. I'm unsure if assumptions about the time-series may clarify the problem better, so ...
0
votes
0
answers
56
views
Product types: algebraic structure for modeling product types with commutative and associative product operation
Is there a known algebraic structure over set of Types (however they are defined) which is equipped with:
commutative and associative product operation for building product types from simpler types, ...
- 1
1
vote
0
answers
114
views
Computing sine of gamma function [closed]
In the sense of bit complexity, how difficult is it to compute $$\sin(a\Gamma(x))$$ where $a$ is a constant and $x>1$? Is it possible to avoid the computation of $\Gamma$ as first step?
Is there a ...
- 12.9k
1
vote
1
answer
195
views
Concentration of a certain simple / well-structured random multilinear polynomial with growing degree
Let $k$ and $N_1$ be positive integers and set $N=kN_1$. Partition $[N] := \{1,2,\ldots,N\}$ $k$ disjoint from $G_1,\ldots,G_k$ of each of size $N_1$, and let $\mathcal T(k,N_1)$ be a transversal of ...
- 63.9k
3
votes
1
answer
98
views
Lattice basis reduction over rings of number fields
Can one use lattice basis reduction algorithms, such as LLL over (low-rank) module lattices over rings of number fields of degree greater than 1? Is there any work on lattice reductions over Euclidean ...
- 1,099
0
votes
1
answer
254
views
Is this kind of functor $\mathsf{Set}/M×\mathsf{Set}/M\to \mathsf{Set}/M$, with $M$ a monoid, a known construction?
I'm trying to construct lists with elements of type $A$ as the initial algebra over a base endofunctor in $\mathsf{Set}/\mathcal{P}(A)$, such that the list is indexed by the set of its elements.
My ...
- 10.7k
1
vote
0
answers
109
views
Problems Correction of "Algebra, Topology, Differential Calculus, and Optimization Theory For Computer Science and Machine Learning "' [closed]
Where I can find the problems correction of this book " Algebra, Topology, Differential Calculus, and Optimization Theory For Computer Science and Machine Learning "
- 11
4
votes
1
answer
291
views
Discrepancy in the calculation of $2$-Selmer group by Magma and LMFDB
The result of LMFDB claims (https://www.lmfdb.org/EllipticCurve/Q/1640/c/1 )
that (2-part of) Tate-Shafarevich group $\mathrm{Sha}(E/\Bbb{Q})$ of elliptic curve $y^2=x^3-8747x-314874$ has order $16$. ...
- 37k
11
votes
1
answer
1k
views
Smale's view of mathematical artificial intelligence
This snippet is from Smale's paper Smale, Steve (1999). "Mathematical problems for the next century". In Arnold, V. I.; Atiyah, M.; Lax, P.; Mazur, B. (eds.). Mathematics: frontiers and ...
- 6,819
2
votes
0
answers
30
views
Free programs suggestions to simulate parabolic EDPs
I'm interested in learning how to computationally simulate the behavior of parabolic partial differential equations, but I don't know where to start, what are the best free programs to use and where ...
- 677
0
votes
2
answers
331
views
Hypergraph cartesian join operation (over same vertex set)
Consider two hypergraphs $H_1 = (V, \mathscr{E}_1), H_2 = (V, \mathscr{E}_2)$ over the same vertex set $V$. am interested in what could be called a "cartesian join" operation building a new ...
- 6,367
4
votes
2
answers
308
views
Concentration of minimum Hamming distance between $N$ points sampled iid from uniform distribution on $n$-dim hypercube $\{0,1\}^n$
Let $n$ be a large positive integer. Sample $N \ge 2$ points $x_1,\ldots,x_N$ iid from the uniform distribution on the $n$-dimensional hypercube $\{0,1\}^n$. Define the gap $\delta_{N,n} := \min_{i \...
- 10.4k
1
vote
1
answer
85
views
Where to find hard instances of subsetsum and other famous np-complete problems for testing heuristics against?
[Can move to cs or tcs stackexchange if thats a better home]
I remember back around 2016 DIMACS used to host a list of problem instances of various famous problems in the NP-complete class and harder ...
- 5,429
2
votes
1
answer
85
views
Example of worst case distributions for 4D convex hull
My understanding is that convex hull of n points in 4D could have O(n²) edges in the worst case. Source: https://sites.cs.ucsb.edu/~suri/cs235/ConvexHull.pdf
This same source writes
In 4D, there are ...
- 151k
4
votes
4
answers
472
views
Automatically generating combinatorial conjectures
It very often happens that one reduces a problem to a bunch of combinatorial data, and need to sift through this data for patterns, which form conjectures on which to do "real" mathematics. ...
1
vote
0
answers
83
views
Convex optimization with one-point feedback
In an adversarial bandit setting, we want to minimize $\sum_{1}^{T}l_t$(not exactly this but the corresponding regret), where $l_t$ is the loss function in the $t-$th round. Each round we can specify ...
- 21
2
votes
0
answers
245
views
Pancake sorting problem – Is computing f(n) NP-hard?
The so-called Pancake flipping problem first discussed by Jacob E. Goodman here yields two entangled problems:
MIN-SBPR (Sorting By Prefix Reversals) - Given a permutation, find the smallest sequence ...
- 51
0
votes
0
answers
59
views
NC0 randomness vs. non-uniformity
In
Ajtai and Ben-Or. A theorem on probabilistic constant depth
Computations. STOC '84, 1984
Ajtai and Ben-Or show a non-uniform derandomization of BPAC0.
Is there a similar relation known for ...
- 869
3
votes
2
answers
517
views
Various notions of Turing reduction for partial functions
If $f$ and $g$ are partial functions $\mathbb{N} \to \mathbb{N}$, define six preorder relations $f \preceq g$ as follows:
$f \mathop{\preceq_{\mathrm{S}}} g$ ("$f$ is strict/Sasso reducible to $g$") ...
- 32.5k
55
votes
17
answers
16k
views
Computer science for mathematicians
This is a big-list community question, so I'm sorry in advance if it is deemed too soft but I haven't seen anything similar yet.
I've seen computer scientists post questions looking to learn things ...
- 4,713
6
votes
2
answers
356
views
Smallest base to reach partial recursive functions as a closure of unbound search
It is customary to define the class of partial recursive functions by taking the set of primitive recursive functions $PR$ and taking closure over unbound search operation.
Do we need the "whole&...
- 4,713
1
vote
1
answer
141
views
Inferring geometric properties of a polytope from intersection volumes of spheres at unknown coordinates on its surface
Let's say we have some polytope $P$ in 3-space (which is not necessarily convex) as well as some number of points on its surface, $(g_1, ..., g_N)$. We are provided no information about the ...
- 2,821
18
votes
3
answers
785
views
Automated search for bijective proofs
In enumerative combinatorics, a bijective proof that $|A_n| = |B_n|$ (where $A_n$ and $B_n$ are finite sets of combinatorial objects of size $n$) is a proof that constructs an explicit bijection ...
- 15.8k
2
votes
3
answers
10k
views
Worst known algorithm in terms of Big-O (more precisely Big-theta)?
Hello,
I have been trying to find the worst algorithm in terms of it's Big-O function. By worst I mean n! is worse than n^2, n^n is worse than n!, etc. Essentially the worst algorithm would be the ...
- 1,446
103
votes
4
answers
5k
views
How feasible is it to prove Kazhdan's property (T) by a computer?
Recently, I have proved that Kazhdan's property (T) is theoretically provable
by computers (arXiv:1312.5431,
explained below), but I'm quite lame with computers and have
no idea what they actually can ...
- 19.6k
13
votes
1
answer
2k
views
The hardness of computing inverse
Say we have a one-to-one (total) function $f:\mathbb{N}\to\mathbb{N}$ and a Turing-machine $T_f$ that computes it. Suppose further that $T_f$ runs in polynomial time wrt. length of the input.
Are ...
- 3,230
19
votes
2
answers
11k
views
Meaning of $\Subset$ notation
The symbol $\Subset$ (occurring in places where $\subseteq$ could occur syntactically) comes up frequently in a paper I'm reading. The paper lives at the intersection of a few areas of math, and I ...
- 259
1
vote
0
answers
64
views
Does Frobenius number increase if bound on input increases?
The Frobenius number F is the largest number not expressible as a non-negative linear combination of some set of positive integers $\{a_i\}$, where, $a_i$ has gcd 1. Denote $maxF(n)$ as the maximum of ...
- 12.3k
0
votes
0
answers
118
views
Conjecture on the unsolvability of the $\{3 \times 3 \times \cdots \times 3\} \subseteq \mathbb{R}^k$ dots problem starting from the central point
In 2020 (see Solving the $106$ years old $3^k$ points problem with the clockwise-algorithm, JFMA, 3(2), p. 96), I conjectured that, in the Euclidean space $\mathbb{R}^k$, we can cover any given set of ...
- 4,786
1
vote
1
answer
537
views
Finding an optimal covering trail for the set $\{0,1,2,3\}\times\{0,1,2,3\}\times\{0,1,2,3\}$
Here is a key question (i.e., Question 2 below) that, if correctly answered, would let me support a very general conjecture on a wide class of related problems, a conjecture that I have never shared ...
- 1,451
3
votes
0
answers
227
views
How rigorously can we apply the data supplied by this nonstandard attack on Kuratowski's closure-complement problem?
Suppose a student assigned an advanced version of Kuratowski’s closure-complement problem to solve—one that leaves out the standard hint about the finite upper bound of $14$—decides to look for the ...
- 12.9k
4
votes
1
answer
362
views
Lower bound on the number of solutions of 2SAT
To compute the number of solutions of a 2SAT is a hard problem. Is there some nontrivial lower or upper bound on this number in terms of a “coarse-grained” description of the Boolean formula, for ...
- 83
15
votes
3
answers
9k
views
$n$-dimensional Voronoi diagram
I need to compute the Voronoi diagram of a set of points in $R^n$.
I'm quite unschooled on the topic, could someone point me to the right references so that I can
a) understand the theory behind it;
b)...
- 63.9k
1
vote
3
answers
1k
views
How can one characterize NP^SAT?
Can you help me understand the class of problems solvable by a nondetermimistic Turing machine with an oracle for SAT running in polynomial time?
- 83
2
votes
1
answer
137
views
Optimal number of half-spaces in the $H$-representation of the convex hull of $n$ points in $\mathbb R^d$
Let $P$ be the polytope obtained as the convex hull of $n$ points in $\mathbb R^d$. This is the $V$-representation of $P$. Note that $P$ can also be represented as an intersection of closed half-...
- 32.1k
3
votes
0
answers
108
views
Hamiltonian path in $\{0,1\}^n$ with rotations and bit-flip in position 0
We consider any non-negative integer as an ordinal, that is $0=\emptyset$ and $n=\{0,\ldots,n-1\}$ for every positive integer. Let $\{0,1\}^n$ denote the set of $\{0,1\}$-vectors of length $n$.
Define ...
- 48.9k