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

2
votes
1answer
239 views

Pumping lemma usage

I need to know if my solution for a problem related with regular languages and pumping lemma is correct. So, let $L = \{a^ib^jc^k \mid i, j,k \ge 0 \mbox{ and if } i = 1 \mbox{ then } j=k \}$ Now i ...
7
votes
2answers
5k views

Computational complexity of computing the determinant

The formula for the determinant of an $n$ by $ n$ matrix given by expansion of minors involves $n!$ terms. As such, computing the determinant of a given matrix of with integer entries via expansion by ...
1
vote
2answers
201 views

Using base-2 numbers: $(1010001)_{2}/(11)_{2}=?$

I wanna solve this simple equation using base-2 number system. $(1010001)_{2}/(11)_{2}=?$ I can't remember how to do that, normally I would start with $101/11$ but what should I do this base-2 ...
1
vote
2answers
740 views

Counting inversions in lists algorithmically

I want to extract useful info from some data and this makes me think how to do it efficiently. I will try to explain the problem with math terms. If we have a sequence of numbers $A=(a_{1}\space a_{2}...
0
votes
1answer
205 views

How one can prove $o(g(n)) \cap \omega (g(n))$ is empty?

From definition of $o$ and $\omega$ one states that $0 < c_1\cdot g(n) < f(n)$ for $n > n_0$ and some $c_1$ and another states that $0 < f(n) < c_2\cdot g(n)$ for $n > n_1$ and some ...
1
vote
1answer
127 views

Partitioning a graph with degrees at most 3

We define a partition of an undirected graph $G=(V, E)$ as some set $A \subseteq V$, which partitions $V$ into $A$ and $V \setminus A = B$. Define $n=|V|$. We call a partition $\alpha$-balanced if $\...
6
votes
2answers
2k views

Every language is regular?

Could anyone tell me the error in my reasoning: The set of strings of a given alphabet is a countable set. Every string can be determined by a regular language. The union of two regular languages is ...
0
votes
1answer
76 views

inapproximability within $1+n^{\epsilon}$

I am a bit confused with the notation of an optimization problem not being approximable within a factor of $(1+n^{\epsilon})$. What exactly does this mean? I am confused because if I (as a user of ...
2
votes
0answers
294 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 ...
3
votes
1answer
367 views

Regular expressions which first disagree after an exponential length

Problem 8.24 of Sipser's Introduction to the Theory of Computation asks: For each $n$, exhibit two regular expressions $R$ and $S$ of length $poly(n)$ where $L(R)\not =L(S)$, but where the first ...
0
votes
1answer
82 views

Can every even natural number n be written as $\sum^N_{i=1}2^i\cdot f(i)$, where $f(i)$ is either zero or one?

This seems like something that should be trivial but I am having trouble showing it.
0
votes
2answers
305 views

Is an abstract machine Turing-complete if it can simulate itself?

For instance, in programming languages it's common to write an X-in-X compiler/interpreter, but on a more general level many known Turing-complete systems can simulate themselves in impressive ways (e....
2
votes
1answer
2k views

Nondeterministic PDA to Deterministic PDA

Are there any resources on how to convert a non-deterministic PDA to a deterministic one, if a deterministic PDA actually exists? Or is there a step by step way on how to do this, kind of like going ...
2
votes
3answers
475 views

Fake Proof that $\mathrm{NP}^\mathrm{NP} = \mathrm{NP}$

I found this faulty proof of $$ \newcommand{\NP}{\mathrm{NP}} \NP = \NP^{\NP}, $$ where the tricky part is to proof that $ \NP ^{\NP} \subseteq \NP$, and this is how it is realized: Take $\NP^\NP$ ...
6
votes
1answer
756 views

Is there a simple algorithm to generate unlabeled graphs?

While working on some other problem I realized I need to generate (not only enumerate!) all unlabeled graph (or exactly ONE representative from each equivalence class of labeled graphs) with a certain ...
1
vote
1answer
3k views

Parity Checking and truth tables

I have a question that I am very confused about. Parity Checking. Produce a truth table for a parity checking circuit that is based on $4$ input data bits, an input parity bit and a single ...
3
votes
1answer
348 views

Properties of computable numbers

If we enumerate* all the computable numbers, those for which there exist a turing machine that outputs its digits to arbitrary precision. What is known about the asymptotic density of rationals, ...
11
votes
2answers
8k views

Reed Solomon Polynomial Generator

I am developing a sample program to generate a 2D Barcode. And i am using reed solomon error correction code. By Going through this article i am developing the program. But i couldn't understand how ...
2
votes
1answer
719 views

Proof that a multiplication verification can be done in log space

In Sipser's Introduction to Theory of Computation, he asks us to show that the language $MULT=\{(a,b,c):ab=c\}$ with $a,b,c\in\mathbb{Z}^+$ can be decided in log space. I originally started out with ...
1
vote
1answer
188 views

Merlin-Arthur complexity class for function problems

Quoting wikipedia, the complexity class $MA$ is the set of decision problems that can be decided in polynomial time by an Arthur–Merlin protocol where Merlin's only move precedes any computation by ...
0
votes
2answers
926 views

bitwise operations

so my question is what is the order of operations for bitwise operators << & | and also to see if my logic is right with the problem below (x03 << x08)+ x00 = 300 ((...
1
vote
1answer
105 views

Searching name for string concatenation problem

I am basically only looking for a name of a problem so I can find information about it. A friend of mine explained it to me like this: Given is a set of string variables $(x_1, \ldots, x_n)$, and a ...
1
vote
1answer
92 views

Size of an NL TM

On page 325 of Sipser, he gives a proof that PATH is NL-Complete which says basically that we can create a graph where each node is a configuration of a TM, and then solving if a path exists ...
9
votes
2answers
2k views

How can I learn about proofs for computer science?

I study computer science at a university. My school offers several courses where various proofs are expected, but there is no course that introduces the fundamental concepts of proofs and how to write ...
17
votes
2answers
2k views

Density of halting Turing machines

If we enumerate all Turing machines, $T_1$, $T_2$, $T_3,\ldots,T_n,\ldots$, What is $$\lim_{m\to\infty}\frac{\#\{k\mid k\lt m \text{ and }T_k\text{ halts}\}}{m}\quad?$$ Or does this depend on how we ...
4
votes
1answer
77 views

Efficiently deciding if any of a set of cylinders in 3-space intersect

Let's say I have a set $C$ of $N$ cylinders in 3-space, $(c_1, ..., c_N) \in C$, where each cylinder, $c_i$, has an associated radius $r_i$ and two coordinates specifying the endpoints of the line ...
2
votes
1answer
729 views

How to determine if a graph is 3-colorable, given a way to determine for any graph if removing an edge from that graph gives a 3 colorable graph?

The question is rather explicit, but I will restate it here: Given the ability to determine whether there is an edge that can be removed from a given graph to give a 3-colorable graph, how can I find ...
1
vote
2answers
165 views

Sequences of a computable function

Is there any computable function $f(n)$, which given any integer $n$ has been proven to return either $0$ or $1$ in finite time, and for which the statement "$f(1), f(2), f(3),\ldots$ contains ...
19
votes
4answers
2k views

Is chess Turing-complete?

Is there a set of rules that translates any program into a configuration of finite pieces on an infinite board, such that if black and white plays only legal moves, the game ends in finite time iff ...
1
vote
0answers
568 views

Regular expression from DFA

I want to create a regular expression from the following deterministic finite automaton using an equivalence system: $\begin{align}L_1 = & \{a\}L_1 &\cup& \{b\} L_2 & \cup & \...
3
votes
1answer
83 views

Equivalences of regular expressions - which one is wrong?

Let $\alpha,\beta \in \text{RA}(\left\{0\right\})$ where $RA(\Sigma)$ is the set of all regular expressions of the alphabet $\Sigma$. The following two equivalences are given: $\alpha\...
1
vote
1answer
165 views

Reduction over intersection of languages

Given two languages $L1$ and $L2$, such that $L2$ is NP-Hard under polytime (many-one or Turing) reduction. Let $L=L1\cap L2$. 1- Is it true that if $L2$ is polytime (many-one or Turing) reducible to ...
25
votes
1answer
658 views

Always oddly-many ones in the binary expression for $10^{10^{n}}$?

Update: Pending independent verification, the answer to the title question is "no", according to a computation of $q(10) = 11609679812$ (which is even). Let $q(n)$ be the number of ones in the ...
0
votes
2answers
116 views

What (formal) language does this describe? And, how do I prove it's regular?

I have this problem that I can't seem to be able to wrap my head around, and I was wondering if there was someone here that could help me understand it. Let $L_1$ be a regular language over $\{a, b, ...
3
votes
2answers
574 views

Time complexity of sorting a partially sorted list

Assume a sorted list of $n$ elements followed by $f(n)$ elements in random order. How would you sort the whole list given the following: a) $f(n)=O(1)$ b) $f(n)=O(\log n)$ c) $f(n)=O(n^{1/2})$ d) ...
3
votes
1answer
156 views

How to intercept someone moving in a 2-dimensional grid world?

Suppose you have a discrete 2D grid where each point represents a person, for example $\mathbf{d} = (x_d, y_d)$. Each person can only move exactly one square up, left, right or down (or stay put) per ...
0
votes
1answer
201 views

inverse polynomial

I am reading from some notes on cryptography and came across this sentence: "We call a function f negligible in k if it asymptotically approaches zero faster than any inverse polynomial in k i.e., $f(...
0
votes
1answer
327 views

Comp Sci Math; Hamming Distance

I've been tasked with this question but I have no idea how to answer it. What is the maximum possible hamming distance between two points from level i in a n-cube?
3
votes
1answer
615 views

Directed Graph, shortest path algorithm. I don't even understand what this question is asking. Is it a trick question or just Dijkstra's?

Consider a directed graph with each edge assigned a nonnegative weight D that reflects the difficulty of passing over that edge (perhaps modeling an obstacle course). Define the difficulty of a ...
2
votes
1answer
268 views

Need to express curves as a set of gaussians, and compare two of these sets

I have two xy curves, defined numerically on a given (potentially different) range of x coordinates. What I need to do is to compare these two curves with the following strategy: express each curve ...
6
votes
1answer
1k views

What about Genetic Algorithms from a mathematical point of view?

Last year I've attended an Artificial Intelligence course (it was very simple, just a summary of the main ideas); we've seen what a genetic algorithm is and the idea seems very interesting to me. Now ...
7
votes
2answers
3k views

Advice for how to learn more advanced math for audio signal processing?

I am very interested in learning about audio from a signal processing standpoint. However, whenever I try to further my education by reading books, I get extremely frustrated because the books use ...
1
vote
2answers
428 views

How do I generate the set of binary strings with elements that are unique under reversal?

What is the most efficient way to generate the set $S$ of unique binary strings of a certain length, $L$, s.t. all strings are unique under the reversal operation? For example, if $L = 2$, the ...
2
votes
1answer
1k views

CRC computation

I would like to understand the CRC computation using CCITT CRC-16 $x^{16} + x^{12} +x^{5} +1$. I was able to successfully implement it in a program but I would like to understand the computation ...
2
votes
4answers
162 views

Regular expression $baa \in a^*b^*a^*b^*$: is that true or false?

Could someone please guide me how to go about solving this problem? $$ baa \in a^*b^*a^*b^* .$$ The question asks whether string $baa$ is an element of $a^*b^*a^*b^*$ (in other words a set of any ...
2
votes
1answer
249 views

Where to find $\lambda$-calculus examples? For instance, how to check if a list is empty?

I'm trying to remove many layers of dust from my knowledge about $\lambda$-calculus, without my notes from classes (several hundreds of km and 5 years away). I was trying to understand the examples ...
4
votes
1answer
723 views

Order of growth proofs?

I was wondering how people go about showing the proofs with orders of growth? Currently, I have the following functions and I know what order they go in, but I'm not sure how to prove them. I simply ...
2
votes
1answer
766 views

Unable to construct Context-free Grammar from Pushdown Automaton

I have a problem in constructing a Context-free Grammar for the Language $$L = \{a^mb^n : m≠n,m>0,n>0\} .$$ Though I can able to construct a Pushdown Automata. I can construct a CFG, but it ...
2
votes
3answers
364 views

Math/CS Algorithm Analysis Question

I've placed this on the Math Stack Exchange even though it is really a CS question because it is the math that is stumping me. Please note, I'm not asking you to do this problem for me, just to make ...
1
vote
1answer
197 views

which class does this function belong to in the fast growing hierarchy?

the class $\mathfrak{F}_k$ of the fast growing hierarchy is the closure under substitution and limited recursion of the constant, sum,projections and $F_n$ functions for $n\leq k,$where $F_n$ is ...