Questions tagged [computer-science]
All mathematical questions about computer science, including theoretical computer science, formal methods, verification, and artificial intelligence. For questions about Turing computability, please use the (computability) tag instead. For numerical analysis, use the (numerical-methods) tag. For questions from scientific computing, use (computational-mathematics).
5,646 questions
0 votes
0 answers
32 views
Determiniing max roundness of number in an array
I'm trying to solve the following Codeforces question (https://codeforces.com/contest/837/problem/D), and I feel like I have a solution that's very close but is probably still over the time constraint....
0 votes
1 answer
67 views
If a graph has at least 3 vertices (A,B,C) and there are 2 paths between A,B as well as 2 paths between B,C prove there is/n’t 2 paths between A,C
An undirected graph G contains at least 3 vertices (A,B,C). A and B have two edge-disjoint paths; B and C also have two edge-disjoint paths. Can I conclude that A and C also have two edge disjoint-...
- 11
0 votes
0 answers
36 views
Can lasso selection in Plotly interactive plots describe rational point density?
I am exploring the number of rational points on $\mathbb{P}^2(\mathbb{})$ with bounded height, for example, height less than or equal to 32. More specifically, I am calculating $$N_{\mathbb{P^2}}(B) = ...
- 13
6 votes
1 answer
232 views
A supplement to "FROM FREGE TO GÖDEL A Source Book in Mathematical Logic, 1879-1931" for developments on type theory and computation
This is a cross-posting from Computer Science SE. (Some background - Its actually the second time I am posting this question here. At the first time I was advised to post it on 'Histoy of maths SE', ...
4 votes
2 answers
328 views
Is there any algorithm which can find a common divisor of two polynomials modulo $p^k$?
Let us consider two monic polynomials $f(X), g(X) \in \dfrac{\mathbb{Z}}{p^k\mathbb{Z}}[X]$. Now, we call $h(X)$ is a divisor of $f(X)$, if there exists a $l(X) \in \dfrac{\mathbb{Z}}{p^k\mathbb{Z}}[X]...
- 4,303
0 votes
0 answers
75 views
Most Important Asymmetric Computational Problems in Mathematics and Beyond.
I’m interested in computational problems that are asymmetric: problems where finding a solution is hard, but verifying a candidate solution is easy. For example, in the approximate nearest neighbour ...
- 793
3 votes
2 answers
118 views
Random partitions by using hash functions?
I am looking for a practical(!) way to create many different random partitions of a large set, and then to identify efficiently into which partition some elements of the set belong. Details $\Omega$ ...
- 2,799
0 votes
1 answer
75 views
One-to-one reduction of $K_1$ to $K$
Let $K_1 := \left\{ x : W_x \neq \emptyset \right\}$ with $W_x := \operatorname{Dom}(\varphi_x)$. Let $K = \{x : \varphi_x(x) \text{ halts}\}$. Intuitively, $K_1$ shuold be many-one reducible to $K$, ...
- 3,595