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

1
vote
2answers
76 views

decidability of $\{x|W_x \text{is different from K in only finitely many elements}\}$

Is the following language decidable? Please explain your argument as I want to learn how such problems must be solved to do the rest on my own. $$\{x \mid W_x \text{ is different from K in only ...
1
vote
3answers
107 views

Is it possible to prove from the definition of big $O$ that $5n^3+7n+1$ is $O(n^3)$?

Is it possible to prove from the definition of big O that $5n^3+7n+1$ is $O(n^3)$? Can this be generalised to any case where you have to (and what is the procedure for working it out?) I guess the ...
0
votes
1answer
140 views

Why is it necessary to use sin or cos to determine heading? (dead reckoning)

Here's the problem: (see pic for problem): https://fbcdn-sphotos-c-a.akamaihd.net/hphotos-ak-ash3/21281_10152793202590262_1804321932_n.jpg You have a robot that is moving forward at a variable rate ...
1
vote
0answers
114 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 ...
2
votes
2answers
158 views

Is the difference of two recursively enumerable sets, reducible to $K$?

Is the difference of two recursively enumerable sets, reducible to $K$? $W_x/W_y=\{z|z \in W_x \& z \notin W_y\}$ $K=\{x|\Phi_x(x) \downarrow\}$ $W_x= \text{dom}(\Phi_x)$
1
vote
2answers
202 views

Decidability and undecidability of a set or language

I want to find out whether the following sets are decidable or not. Generally speaking, what exactly should be done about it? Doing some research, I think a language or set is decidable if a Turing ...
2
votes
1answer
118 views

An interesting version of the problem “balls into bins”

Consider n people, each has k identical balls. Each people choose k different bins from m bins, constrained by the condition that there are no two people choose exactly the same k bins. For instance, ...
0
votes
1answer
131 views

Rice’s theorem and recursion theorem

Prove Rice’s theorem using recursion theorem. I need some hints as to what must be done about it. Please use Davis' book notation: Computability, Complexity, and Languages, Second Edition: ...
1
vote
2answers
125 views

non-recursive function

Give a direct proof that the set $\{x|\Phi_x(1) \downarrow\}$ (which is a set of program numbers that halt on input $1$) is not recursive. I've got an idea that indirect proof must work. Assuming ...
1
vote
1answer
287 views

Logical Conjunction of Binary Decision Diagrams

Compute a Binary Decision Diagram for $B1∧B2$. Furthermore, for an arbitrary BDD B you can use the equations $B∧F=F$, $F∧B=F$, $B∧T=B$ and $T∧B=B$. To construct the BDD i start from the leaves ...
2
votes
2answers
56 views

If $\{w^k|w\in L\}$ regular implies L regular?

If L is a language and the language $$\tilde{L}:=\{x^k,x\in L, k\in\mathbb{N}\}$$ is regular, does that imply that L is regular? ($|L|<\infty$ gives equivalence) We came across this question when ...
1
vote
1answer
66 views

Are these two context free grammars equivalent?

Let Σ = {a,b}. A CFG for the language {a^nb^m | n > 2m} can be written as: S-->aaSb S-->A A-->aA A-->a Would it be equivalent to write this CFG as: ...
1
vote
1answer
96 views

to find disconnected graphs

We know that if in a graph $G$, $e$ < $(n -1)$, then the graph is disconnected, where $e$ and $n$ are number of edges and number of vertices resp. Is there any other criteria to find out the ...
1
vote
1answer
126 views

Multivariable asymptotic analysis?

Show that $k \ln k = \Theta (n)$ implies $k = \Theta (n /\ln n)$. Thanks for the help.
0
votes
1answer
697 views

Is the function $\lceil\lg \lg n\rceil!$ polynomially bounded?

I'm totally lost so please be really explicit in your answers. Thanks for the help. Polynomially Bounded: $f(x)$ is polynomially bounded if for some constants $c$, $a$ and $x_0$, $$f(x) \le cx^a$$, ...
1
vote
0answers
37 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
2answers
109 views

Decimal Floating Point to Shortest Binary

Might be more of a Comp Sci question so apologies if it's not appropriate. Basically I have a range bounded by two floating-point decimals <1. I need to find a short binary number lying between ...
1
vote
1answer
138 views

Binary Decision Diagram of $(A\Rightarrow C)\wedge (B\Rightarrow C)$?

I made a Binary Decision Diagram for $(A\vee B)\Rightarrow C$, which i think is correct. Know i want o make a Binary Decision Diagram for $(A\Rightarrow C) \wedge (B\Rightarrow C)$ but i can't. I ...
0
votes
1answer
46 views

Given a DFA $\mathcal{M} = (S, \Sigma, q_0, \delta, F)$, is there an algorithm that finds the pumping length of $L(\mathcal{M}$)?

This question has been bugging me for a while, and I'm curious what such an algorithm would look like, if it exists. My guess is that it does exist, but I'm not sure how it would look.
2
votes
2answers
163 views

An NFA with $\Sigma = \{1\}$ with $x^2$ accepting runs on strings $1^x$ for all $x \geq 0$ - how to construct?

One of my homework assignments requires us to construct an NFA over the alphabet $\{1\}$ which has exactly $x^2 + 3$ accepting runs over the input string 1^x for all $x \in \mathbb{N}$. Now, the +3 ...
1
vote
1answer
60 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 ...
0
votes
1answer
31 views

How can i bound the largest edge length of an $n$-point metric in $O(n)$?

For a given metric $d$ on a finite (vertex) set $V$, how can I bound the largest edge length in $O(|V|)$? While (wlog) assuming that the smallest edge length is at least $1$.
0
votes
1answer
839 views

closest pair in N-Dimensional

I have to find the closest pair in n-dimension, and I have problem in the combine steps. I use the divide and conquer.I first choose the median x, and split it into left and right part, and then find ...
7
votes
2answers
222 views

maximum number of edges to be removed to possess a property

I am working on a problem. We know that on squaring a cycle, degree of every vertex is 4. For squares of cycles, we know if we delete any arbitrary edge then still eccentricity is same for all ...
1
vote
2answers
93 views

Could graph theory aid in the understanding of comparison sorting algorithms?

I am interested in computing the exact number of comparisons that are needed to sort a list. See this wikipedia article. Up to $n=15$, we know how many comparisons between elements one must make to ...
3
votes
1answer
305 views

diameter and radius of a regular graph

I am trying to find the radius and diameter of a regular graph $G$ with $d(v_i) < (n-1)/2$. I know for $d(v) \geq (n-1)/2$, $\rm{diam}(G) \leq 2$ and $\rm{radius}(G)=\rm{diam}(G).$ If we are not ...
2
votes
1answer
66 views

Unique sequences from different sets

I am given $n$ sets with a selection of $m$ elements, such as: $$S = \{\{0\}, \{1, 2, 3\}, \{1, 2, 3\}, \{3\}\}$$ I am trying to calculate the number of unique sequences that contain all elements ...
0
votes
1answer
91 views

Recurrence relations by forward substitution help

My question is to solve the following using recurrence relation forward substitution then verify using mathematical substitution: $T(n) = 2T(\frac{n}{3})$ for $n > 1$, where $n$ is a power ...
3
votes
1answer
303 views

Help with Recurrence relations forward substitution

Thanks in advance to anybody who can help, The question: solve by recurrence relation using forward substitution and verify by mathematical induction. $T(n) = 2T(n/7)$ for $n > 1, n$ is a power ...
0
votes
1answer
237 views

Godel number and expressibility [duplicate]

how to show that these properties of strings of symbols are expressible: 1) being a term, 2) being a formula 3) being a sentence 4) being a proof in PA and where a property (i.e., predicate) P of ...
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
534 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
394 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
198 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
96 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
164 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
536 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
110 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
61 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
327 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
287 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
751 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
265 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 ...