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 ...

learn more… | top users | synonyms

11
votes
3answers
288 views

What is necessary to exchange messages between aliens? [closed]

Lets assume that two extreme intelligent species in the universe can exchange morse code messages for the first time. A can send messages to B and B to A, both have unlimited time, but they can not ...
8
votes
2answers
108 views

Can the rank of the homology group of an abstract simplicial complex be computed in polynomial time?

I want to write a function that does the following: Input: An integer $n$ A function $f$ that maps nonempty subsets of $\{1, \dots, n\}$ to "yes" or "no" such that (a) every singleton set gets ...
2
votes
3answers
529 views

Polynomial bounds?

Q1: Is the function $$\lceil{\lg n}\rceil!$$ polynomial bounded? Q2: Is the function $$\lceil{\lg\lg n}\rceil!$$ polynomially bounded? $$\lg = \log_2$$ Polynomially bounded: $f(n)$ is polynomially ...
1
vote
1answer
390 views

how discrete mathematics is related to computerscience

I have this basic question for sometime since i came across discrete mathematics, hence this question. How discrete mathematics is related to computer science. How its notions are used in the field of ...
0
votes
1answer
196 views

Expressibility and numbering

A predicate $P$ is expressible (in PA) if there exists a formula $\phi(x_1,\ldots, x_n)$ of $L_A$ such that for all $m_1,\ldots, m_n$ elements of $\mathbb{N}$, we have that $P(m_1,\ldots, m_n)$ holds ...
1
vote
1answer
178 views

Second incompleteness and Model theorey

If we let $T$ be a consistent theory in the language of arithmetic $\mathcal{L}_A$ theory extending Peano Arithmetic — with specified numbering of formulas $\left[\cdot\right]$ and suppose that ...
2
votes
2answers
106 views

eccentricity in vertex transitive graphs

I am trying to prove the following.. If $G$ is a veretx transitive graph, then how can we prove that eccentricity of every vertex is same? Getting no idea from where to start? How to prove the same ...
1
vote
1answer
94 views

Why no cut-vertices or cut edges in a graph where eccentricity is same for all vertices

I need help to prove the following statement. There are no cut-vertices or cut-edges(bridges) in a graph where eccentricity is same for all vertices. I am getting that if the graph contains a ...
1
vote
1answer
162 views

Bit permutations and collisions of compression function

I'm having trouble finding a good method for solving the following problem: If $n$ is a positive integer, let $S_n$ denote the group of permutations of the set $\{1,2,\dots, n\}$. For a permutation ...
0
votes
0answers
91 views

How would I create a birthday attack? (Hash Functions)

I'm trying to create an birthday attack, but I can't seem to get through it as I've never done it before. The basis: We have $E_K$, an encryption function, which has $N$ possible keys $K$, $N$ ...
2
votes
2answers
515 views

Are axioms and rules of inference interchangeable?

There is an equivalence between cellular automata and formal systems, you can code one into the other and vice versa. But in the the cellular automata (CA) the rules of inference are fixed and are ...
3
votes
1answer
108 views

The graphs in which radius is equal to diameter

I was working out on a problem. Came out with a result in $C_n$: radius = diam. Worked out on other few graphs where radius=diam. Can we generalize the result? A little hint will be helpful. The ...
2
votes
2answers
60 views

Question about what it means to be in “NP”

Suppose I am trying to prove language $L$ is in NP. Does it suffice to construct a nondeterministic Turing machine that accepts all strings in the language in polynomial time? Or must the machine ...
1
vote
2answers
320 views

Prove asymptotic bound?

Prove: $$n^b = \mathcal{o}(a^n)$$ for and constants $b$ and $a$, where $a > 1$. The book states that: $$\lim_{ n \rightarrow \infty} \frac{n^b}{a^n} = 0$$ The book doesn't prove the limit ...
4
votes
2answers
278 views

What is the fastest computational graph theory package?

What is the fastest computational graph theory package with respect to executing algorithms and computing graph theoretic data? I am aware of this related question, which requests graph theory ...
1
vote
1answer
47 views

Dynamic Programming Trouble, Optimizing time

A robot goes from terminal to terminal collecting bolts. The robot needs to collect at least $m$ bolts and there are $n$ terminals. Terminal $i$ gives the robot a certain number of bolts denoted by ...
1
vote
1answer
740 views

Using mathematical induction to show that a binary tree of height $h$ has no more than $2^h$ leaf nodes

Use mathematical induction to show that a binary tree of height $h$ has no more than $2^h$ leaf nodes. I'm familiar with mathematical induction proofs, but I haven't encountered one like this. ...
2
votes
0answers
164 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 ...
10
votes
3answers
259 views

Why isn't NP = coNP?

Suppose a language L is in NP. I think that means a nondeterministic Turing machine M can decide it in polynomial time. But then shouldn't it be in co-NP, because can't we define a new Turing machine ...
1
vote
0answers
25 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 ...
3
votes
0answers
92 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 ...
0
votes
1answer
378 views

Proving By reduction from the Halting Problem

I want to solve the following exercise in Computability and Complexity Theory: By providing a reduction from the HALTING problem to REACHABLE-CODE, prove that REACHABLE-CODE is undecidable. ...
2
votes
3answers
247 views

Beyond Goedel incompleteness and lack of soundness/completeness of higher-order logics

As I understand that there are at least two fundamental limits of the development of the mathematics: 1) Goedel incompeleteness theorems (or more clearly Church thesis) effectively says that there ...
3
votes
0answers
82 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
1answer
686 views

Eccentricity of vertices in a graph

This question is related to my last question about regular graphs Eccentricity of vertices in a regular graph. I got the required answer but I am having a doubt. Can we put restriction on number of ...
3
votes
0answers
170 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 ...
0
votes
1answer
31 views

Flop computation clarification

Can someone clarify this for me? Suppose I wanted to use MATLAB to compute a polynomial, i.e., $(x-3)^{5}$. Would this count as 5 subtractions and 4 multiplications, or does the computer only subtract ...
7
votes
1answer
269 views

A Mathematical way to represent a image kernel?

How to represent the calculation in this image mathematically? For example: With the discrete convolution and Fourier Transform. It tries to do a calculation on the original image (image A/input) ...
1
vote
1answer
114 views

Big $\mathcal{O}$ notation for multiple parameters?

The following is an excerpt from CLRS: $\mathcal{O}(g(n,m)) = \{ f(n,m): \text{there exist positive constants }c, n_0,\text{ and } m_0\text{ such that }0 \le f(n,m) \le cg(n,m)\text{ for all }n ...
0
votes
1answer
39 views

Are these two definition equivalent?

$f(n) = \mathcal{o}(g(n))$ if for any constant $c$, there exists some constant $n_0$ such that $0 \le f(n) \le cg(n), n \ge n_0 $ $f(n) = \pi(g(n))$ if for any constant $c$, there exists ...
2
votes
1answer
62 views

Proof of algorithm refinement

I recently had an interview in which I was asked to produce an algorithm to that computes the pairs of integers, from a list, that add up to a integer k. I then had to increase the time efficiency of ...
2
votes
1answer
39 views

Fragemented linear feature alignment technique

I am having set of linear features lie on a plane (it does not a matter whether the pane is vertical or horizontal). all linear features are either parallel or othogonal to the vertical axis or ...
0
votes
3answers
77 views

Induction to prove $2n + 3 < 2^n$

I am having trouble and was wondering if someone could go over the steps slowly to show that: $$2n + 3 < 2^n \ \text{for} \ n \geq 4$$ Any help would be amazing!
2
votes
1answer
124 views

Pumping Lemma problem

Apply pumping lemma to each of these and prove that they are not regular. $L = \{ (0^p)(1^q)2 \mid 0 < q < p\}$ $L_2 = \{ (a^p)(b^q)(c^r) \mid p = q \text{ or } q = r\}$ Here my ...
1
vote
1answer
85 views

Decidability Turing Machine Problem

$L=\{G|G$ is a context free grammar over ${a,b}$ and $L\{G\}$ contains at least one string $w$ such that the number of $a$'s in $w$ is a multiple of $5\}$ Show that L is decidable by ...
3
votes
2answers
257 views

Eccentricity of vertices in a regular graph

I was just trying to find out the eccentricity of the vertices in regular graphs, given in the link http://www.mathe2.uni-bayreuth.de/markus/reggraphs.html#CRG. Surprisingly, eccentricity is the same ...
3
votes
1answer
242 views

Lloyd's algorithm in normed vector spaces

How do I run Lloyd's algorithm in a normed vector space? The space: L*a*b* color space, finite sRGB segment, $R^3$ The distance metric: CIE94 using L*C*h* information derived from the L*a*b* ...
2
votes
0answers
151 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 ...
0
votes
1answer
72 views

Algorithm to check if a matrix is elementary

I'm currently writing a homework problem for a linear algebra course and I'm trying to come up with an algorithm to check if a matrix is elementary. That is, to check if it is one of the three forms ...
1
vote
1answer
112 views

Latent Dirichlet allocation

I am currently trying to understand Blei, Ng and Jordan 2003 JMLR paper "latent Dirichlet allocation". In section 3 page 997 I don't understand how to get to equation 3. The paper says "integrating ...
2
votes
3answers
352 views

angle between two intersected plane

If two planes are intersected by making a straight line, like $AB$ then Does the angle between two planes (see figure) always given by the angle between normal vectors ($n_1$ and $n_2$) ?
2
votes
1answer
537 views

Friendship paradox demonstration

I should demonstrate the friendship paradox using the graph theory in this way: The social network graph is represented by an adjacency matrix $a_{ij}$ ($m$ is the number of edges, $n$ is the number ...
2
votes
1answer
90 views

Is there a problem with this example?

In example $1.14$ on page $51$ (of the book and $64$ of this link), shouldn't the string $01000$ get rejected? However it seems that the first three digits of the string would force it to an accept ...
2
votes
2answers
173 views

How to get angle bewteen two vectors in range -1 to 1 without using arc cosine?

Given two normalized vectors in 3d space, how can I get a value from $-1$ to $1$ based on their angle without using arc cosine? With use of arc cosine, I think this would give me the correct result. ...
2
votes
1answer
50 views

Proving non CFL with pumping lemma

I can't seem to figure out how to prove this as not a CFL: $$\left\{x^{a}y^{b}\mid a=kb\space\text{for some positive integer k}\right\}$$ I've tried a bunch of "s"'s to pump such as $a^{2p}b^{p}$ ...
4
votes
2answers
3k views

Finite automaton that recognizes the empty language $\emptyset$

Since the language $L = \emptyset$ is regular, there must be a finite automaton that recognizes it. However, I'm not exactly sure how one would be constructed. I feel like the answer is trivial. ...
4
votes
2answers
504 views

Push down automata problem

Informally describe the Nondeterministic PDA that generates: $$\{x\#y\ \mid x,y\in\{a,b\}^{*}\text{and}\space x\ne y\}$$ My initial plan was to use nondeterminism to go through each character before ...
3
votes
1answer
85 views

Context free language problem

I'm trying to find an unambiguous context free language for the ambiguous language: $$S\rightarrow AB$$ $$A\rightarrow Ba| b$$ $$B \rightarrow aA|b$$ I understand the language makes up of strings ...
6
votes
2answers
1k views

Mathematical way of determining whether a number is an integer

I'm developing a computer program, and I've run into a mathematical problem. This isn't specific to any programming language, so it isn't really appropriate to ask on stackoverflow. Is there any way ...
0
votes
0answers
46 views

Deriving the fundamental equation relationship

I'm having a hard time understanding how a few equations are being derived. So the fundamental equation is an equation that relates corresponding points in stereo images. Anyway, that's the basic ...