# Tagged Questions

All mathematical questions about Computer Science, including Theoretical Computer Science, Formal Methods, Verification, Logic in Artificial Intelligence, and Numerical Analysis

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 ...
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 ...
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)$ ...
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 ...
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?
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 ...
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 ...
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$ ...
0answers
60 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 ...
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 ...
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 ...
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$ ...
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 ...
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 ...
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 ...
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 ...
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 ...
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? ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
0answers
45 views

### Multivariable asymptotic analysis?

Show that $k \ln k = \Theta (n)$ implies $k = \Theta (n /\ln n)$. Thanks for the help.
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
0answers
88 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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
0answers
59 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: ...
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 ...
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 ...
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 ...
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 ...
0answers
97 views

### How is the loop invarient obtained in this square root bound finding algorithm?

Consider the following algorithm. ...
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 82, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9137512445449829, "perplexity_flag": "middle"}