All mathematical questions about Computer Science, including Theoretical Computer Science, Formal Methods, Verification, Logic in Artificial Intelligence, and Numerical Analysis
5
votes
0answers
82 views
$X^A \equiv B \pmod{2K + 1}$
I recently found this problem which asks you to find an algorithm to find all $X$ such that $X^A \equiv B \pmod{2K + 1}$.
Is there something special about the modulus being odd that allows us to ...
4
votes
0answers
110 views
Is there a polynomial-time algorithm to find a prime larger than $n$?
Is there a polynomial-time algorithm to find a prime larger than $n$?
If Cramér's conjecture is true, we can use AKS to test $n+1$, $n+2$, etc. until the next prime is found, and this method will ...
4
votes
0answers
93 views
Calculating $\sum_{y=0}^x \Pr[Y= y] \Pr[Z\leq k-y]^2$ when Y,Z are binomially distributed?
Remark: I recently rewrote this post, hoping to get answers!
I am analyzing the following experiment:
Pick an $x \in \{0,\ldots,2k\}$ uniformly at random
Pick $(2k+1)$-bit bitstring $b_1=(u,v_1)$ ...
4
votes
0answers
129 views
algorithm for solving diagonal quadratic equations over real or complex numbers
I found the following statement in the paper http://www.math.uni-bonn.de/~saxena/papers/cubic-forms.pdf (page 22, in the middle):
For $\mathbb F\in\{\mathbb R, \mathbb C\}$ and $b, a_i\in\mathbb ...
4
votes
0answers
231 views
how can i prove that square root of n is space constructible
I know that square-root of n is space-constructible.
I can't prove it by the space-constructible definition.
How can I show that only $\sqrt{n}$ space is used?
3
votes
0answers
71 views
Which takes more energy: Shuffling a sorted deck or sorting a shuffled one?
You have an array of length $n$ containing $n$ distinct elements. You have access to a comparator on the elements (a black-box function that takes $a$ and $b$ and returns true if $a < b$, false ...
3
votes
0answers
65 views
Binomial Coefficients optimization
Given n and R, I have to find the minimum value of k such that:
$${(2^n)-1 \choose k}\bmod(2^n)==R$$
Where $k = \{0, 1, 2, \dots, 2^n-1\}$
Here ${n \choose k}$ is the binomial coefficient ...
3
votes
0answers
36 views
Covering $n$ points with fewest disks with fixed radius $\epsilon$
The title says it all. I have a set of $n$ points in $\mathbb{R^{2}}$ and I am looking for an algorithm that tells me the fewest numbers of disks of radius $\epsilon$ that cover the set of $n$ ...
3
votes
0answers
61 views
Existence of a general-purpose (almost) universal optimization strategy
From Wikipedia about interpretations of no free lunch theorem
A conventional, but not entirely accurate, interpretation of the NFL
results is that "a general-purpose universal optimization ...
3
votes
0answers
132 views
Amortized Analysis for (2,5)-Tree
I need some help with the following problem
Definition: A (2,5)-tree is an external search tree, where all leaves have the same depth. Each inner node in a (2,5)-tree has at least 2, and at most 5 ...
3
votes
0answers
125 views
Help understand $\text{handle}$ in parsing problem
The BNF is defined as followed:
S -> aAb | bBA
A -> ab | aAB
B -> bB | b
The sentence is:
aaAbBb
And this is the ...
3
votes
0answers
276 views
Constructor And\Or-graph on function transition of the alternating automata
In a And\Or-graph induced by the transition function, each node of G corresponds to a state q belonging to set Q of the state of the Automaton, for q with $\delta(q,a)=q1*q2$, the node is a $*-node$ ...
3
votes
0answers
122 views
Hardness of perimeter minimization?
Given $xy=C$ where $x, y$ are integer variables and $C$ is integer constant.
What is the most efficient algorithm that finds $x,y$ such that $x+y$ is minimum?
Providing references is highly ...
2
votes
0answers
56 views
Max - Flow and Min - Cut, Minimize the number of visible boxes
Suppose that you are given a set of boxes, with each box as a rectangular parallelepiped with side lengths as (i1, i2, i3). And each side length is between half a meter and one meter.
How should a ...
2
votes
0answers
46 views
Boltzmann machines - motivation for the energy function
I've been studying Boltzmann machines lately and was wondering if anyone could give me a "high-level" explanation or motivation for the energy function used:
$$E = -\sum_{i<j} w_{ij} \, s_i \, s_j ...
2
votes
0answers
35 views
Upper bound for linear function
What may be more surprising is that when $a>0$, any linear function $an +b$ is $\mathcal{O}(n^2)$ which is easily verified by taking $c = a + |b|$ and $n_o = \max (\frac{-b}{a}, 1)$.
$$an + b ...
2
votes
0answers
119 views
2-Player Game PSpace-Completeness
So there is a n x n game board and each location on the board has an integer. Player one picks a number from row 1 and player 2 picks a number from row 2 and they alternate until there are no more ...
2
votes
0answers
113 views
1/3+2/3 in double precision
When I add 1/3 and 2/3 in double precision, I ended up with $1.\boxed{111\ldots1}1\times2^{-1}$, where the boxed part is the 52-bit mantissa. By the rounding to even rule, I should round it up, right? ...
2
votes
0answers
57 views
Embedding tree metric isometrically into $\ell_\infty$
I just started (independent) learning on metric embeddings from the Fall 2003 offering of the course at CMU. I have a limited mathematical background and alas, it made me stumble at the first exercise ...
2
votes
0answers
159 views
Approximate Set Cover Problem by Rounding
Here is the simple algorithm for approximating set cover problem using rounding:
Algorithm 14.1 (Set cover via LP-rounding)
Find an optimal solution to the LP-relaxation.
Pick all sets ...
2
votes
0answers
160 views
The minimal number of states required to run Goldbach's Conjecture
It is well known that being able to compute Busy Beaver numbers would allow one to solve (in theory) such open problems as Goldbach's conjecture. Simply run a Turing machine with $n$ states to check ...
2
votes
0answers
143 views
Further question on “uncountable” Turing Machine
Having read An "uncountable" Turing Machine? I have further questions that I don't believe it addressed. (I'm a programmer, not a mathematician so I apologize if this is stupid or the ...
2
votes
0answers
65 views
How to prove that untyped $\lambda$ and simply typed $\lambda$ are of diferent expressive powers
How to prove that untyped $\lambda$ and simply typed $\lambda$ are of diferent expressive powers, using category theory?
I'm just getting to grips with the basic ideas of category theory, and I'm ...
1
vote
0answers
28 views
Pebble game on graph
Consider the problem whose instance is a directed graph with the selected vertex V and k of 'pebbles'. We can in any order, perform the following elemental steps:
on top of x we can put a pebble, if ...
1
vote
0answers
45 views
Multivariable asymptotic analysis?
Show that $k \ln k = \Theta (n)$ implies $k = \Theta (n /\ln n)$.
Thanks for the help.
1
vote
0answers
27 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 ...
1
vote
0answers
13 views
Prefix relation on words in $\Sigma^*$ - why does a maximum element imply that the prefix relation is a linear order?
I'm currently preparing for a test, and I'm having trouble understanding one of the preparation questions. The question is as follows:
Let $\Sigma$ be a finite alphabet. The prefix relation on words ...
1
vote
0answers
11 views
Confusion related to Kulldorff's scan statistics
I was reading this paper related to Bayesian spatial scan statistics where I came across the Kulldorff's scan statistics.
I have attached the screenshot of the paper. My objective is to find a ...
1
vote
0answers
37 views
Mean matching size
Suppose there is a simple bipartite graph $G(X,E,Y)$, where $|X|=n_1$, $|Y|=n_2$, $|E|=m$. The edges $E$ are chosen uniformly at random.
The question is what is a mean value of the size of the ...
1
vote
0answers
13 views
Lower bound on building heap.
A lower bound of the needed number of comparision to build a heap is given by GASTON H. GONNET and J. IAN MUNRO as following
THEOREM 4. $1.3644... n + O(lg n)$ comparisons are necessary, not only ...
1
vote
0answers
36 views
Good reference for co-groups, perspective of co-algebra applications
There are lot of applications of state transition systems STS (computer science, planning problems in robotics and so on) and lot of algorithms are devised, but the mathematical background for STS is ...
1
vote
0answers
35 views
Regression with multiple line types from set of points
Given a set of points, I'm looking to find the best possible line (within reason) to fit to these points. These points won't be from real data, so they could form any sort of curve or line. So, I ...
1
vote
0answers
64 views
Asymptotic analysis for multiple variables?
How is asymptotic analysis (big o, little o, big theta, big theta etc.) defined for functions with multiple variables?
I know that the Wikipedia article has a section on it, but it uses a lot of ...
1
vote
0answers
84 views
PDA state diagram with an inifinite languge but with no looping states
For class I'm supposed to create a PDA state diagram that is capable of generating an infinite language with no state q such that q is reachable from the start state, there is no cycle within the ...
1
vote
0answers
31 views
LTL translation to Omega regular languages
I tried to define a translation from LTL to ω-regular languages. I built it inductively on the structure of LTL formulae. No problem except with the 'until' operator where I came up with the ...
1
vote
0answers
1k views
Introduction to the Theory of Computation Solution Manual - Michael Sipser
I am hoping to test out a Theory of Computation class for next semester and have bought the course's textbook, Introduction to the Theory of Computation by Michael Sipser to prepare. I was trying to ...
1
vote
0answers
148 views
Diffie-Hellman key exchange public key calculation
I encountered a question that I can't seem to get around it. Lets say user A and B uses the DHKE defined over $GF(2^8)$ induced by the irreducible polynomial $x^8 + x^4 + x^3 + x^2 + 1$ and the ...
1
vote
0answers
89 views
Power sums, fast algorithm
I know some schemes to compute power sums (I mean $1^k + 2^k + ... + n^k$) (here I assume that every integer multiplication can be done in $O(1)$ time for simplicity): one using just fast algorithm ...
1
vote
0answers
84 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={(m_{ij})}_{i=1,...,n,\ j=1,...,k}$, where ${m}_{ij}$ is the greates common divisor of $i$ and ...
1
vote
0answers
76 views
What was done to calculate the Ramsey numbers using a quantum computer?
I recently came across this paper titled
Experimental determination of Ramsey numbers with quantum annealing
I was wondering what exactly the gist of the paper, as I read it, it seems rather ...
1
vote
0answers
99 views
Calculating step value in range slider using density distribution
I have a javascript range slider with minimum value 0 and maximum value 133K.
My initial problem is that this javascript range slider goes up by a step value of 1, meaning that it is relatively ...
1
vote
0answers
52 views
How to prove a property of the Lawvere theory for global state
In the field of algebraic computational effects, there is a Lawvere theory for global binary state (taking value either $0$ or $1$) which is generated by three operations
$get: 2 \to 1$
$put_0: 1 ...
1
vote
0answers
101 views
1s surpassing 0s in binary strings of odd length
Let $A(k)$ be the number of distinct binary strings of length $2k+1,$ for which the number of $1$s surpasses the number of $0$s for the first time at digit number $2k +1$, i.e., in the final digit in ...
1
vote
0answers
75 views
Historical relation between computer science and the theory of dynamical systems
I wonder if there is any historical relation between the fields of Dynamical systems (and related fields such as Optimal control) and (theoretical) Computer science. The reason for which I ask this ...
1
vote
0answers
60 views
How are the various numbers in the standard 2.2 gamma correction for RGB derived?
Here is the standard fwd Gamma 2.22 (1 / 0.45) correction formula:
...
1
vote
0answers
313 views
An algorithm to convert float number to binary representation
I want to know the algorithm of converting a given float (e.g, 3.14) to binary in the memory.
I read this wikipedia page, but it only mentions about the conversion the other way.
Let me quickly give ...
1
vote
0answers
69 views
Need little hint to prove a theorem .
I have an iterative method \begin{eqnarray}
X_{k+1}=(1+\beta)X_k-\beta X_k A X_k~~~~~~~~~~~~~~~~~ k = 0,1,\ldots
\end{eqnarray}
with initial approximation $X_0 = \beta A^*$ ($\beta$ is scalar ...
1
vote
0answers
198 views
Polynomial-Time reduction: Clique Problem
Here is an exercise my friend proposed to me:
Show that the maximum clique problem polynomial time reduces to the maximum independent set problem.
Here is my attempt at solving it:
It is known ...
1
vote
0answers
126 views
what is the relationship between the complexity class E(and EXP) and NP?
I want to know any relationship between the complexity class E(and EXP) and NP.
I also would like to know whether there is any $DTIME$ formulation or relations of $NTIME(O(n^k))$ where n is the size ...
1
vote
0answers
97 views
How is the loop invarient obtained in this square root bound finding algorithm?
Consider the following algorithm.
...
