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
53 views

Number of trees of a certain size

Given a branching factor $b$ and a tree height $h$, a complete tree has $\sum_{i=0}^h b^i$ nodes. Define a partial tree as a sub-tree of the complete tree, with the same root. How many such partial ...
3
votes
4answers
226 views

Algorithm Analysis: How to simplify a summation leading up to a maximal term?

Okay so I have a summation which goes: $$\sum_{i=1}^{n^3} 3i^2\cdot\log(i)$$ My goal is to find the order of the function, not the exact summation amount. I have found the order of it by writing ...
1
vote
1answer
72 views

What's wrong with this argument for $NP \ne EXP$?

Let $\{M_i\}$ be any enumeration of all Turing machines in which each machine appears an infinite number of times. Consider the language $D = \{i \, | \, M_i(i) \text{ does not accept within ...
6
votes
2answers
214 views

Relatively prime property verification

I am reading a computer science puzzles book. And I get the following question - "You have a five quart jug, a three quart jug and unlimited supply of water. How would you come up with exactly four ...
4
votes
0answers
132 views

Computational hard math problem

Given a square filled randomly with the numbers $1$ to $N$, for instance $$\begin{array}{cccc} 16 &12 & 9 & 1\\ 11 & 3 & 4 & 7\\ 2& 8 & 5&14\\ 6& 10& ...
0
votes
1answer
63 views

Is this language context free and if it is which grammar generates it?

$$L=\{\, w \in\{a,b,c\}^* :w=a^ib^jc^k, j=\max\{i,k\}\,\}$$ I think I proved it not context-free using pumping lema for CFL, but I'm not sure I'm doing it right. So, if someone knows grammar that ...
3
votes
1answer
316 views

An alternate analysis to the (worst-case) run time of the euclidean algorithm

I was trying to figure out the running time of the euclidean algorithm. The analysis that I found on Wikipedia and CLRS both analyze the run time of the euclidean algorithm using the Fibonacci ...
1
vote
1answer
56 views

Languages in P that are not P-complete

Why aren't there any languages in P that are not P-complete?
0
votes
0answers
70 views

How to check if a function is negligible?

Let $\epsilon(x)$ be a negligible function. Let $p$ be a polynomial such that $p(k) \geq 0$ for all $k > 0$. What can we say about $\epsilon(p(k))$? Is this a negligible function? If yes, ...
0
votes
1answer
27 views

Determining if a problem is solvable by a Push-Down Automaton

I have the following language: {0^n 1^n 0^n 1^n | n >=0} And need to find a PDA that recognizes the language. I have devised PDAS which determine ...
1
vote
0answers
58 views

Theory of Automata concepts

I just started taking Theory of Automata and I'm having a hard time understanding some of the concepts. It's been only a week and the following questions are my homework. I'm not asking you to do my ...
0
votes
3answers
153 views

Distance between pixel centres on a tv

I have a question i am stuck on in my maths class. I am going to change the numbers so i can figure it out this example myself. Need to get the distance between the two pixels calculated. Thanks ...
0
votes
3answers
43 views

Reference for problems without efficient algorithm (in polynomial time)

I'm writing paper and need your help in finding some famous (or not so famous) problems without efficient algorithm, but from logic or computer science. So far, I have: -Boolean satisfiability ...
2
votes
1answer
50 views

Strong primes in cryptography, their relation to complexity theory and security

According to the lecture slide by Shafi Goldwasser a prime is a strong prime if: $$p = 2q + 1$$ for some prime q. For me it, seems a bit arbitrary that is the definition of a strong prime in ...
0
votes
3answers
191 views

Acyclic graph - source node

How can I prove that a directed acyclic graph has a source node? A node 'a' is called source node if doesn't exists edges like ('b','a').
2
votes
0answers
99 views

Implications of NP=coNP for PSPACE

If NP = coNP, then the Polynomial Hierarchy collapses to its first level (NP). Intuitively, it seems to me that PSPACE should collapse down to NP as well. As a loose heuristic argument, take the ...
2
votes
1answer
152 views

Subsets of all Diophantine's sets

Function $\mathbb{N}^k \to \mathbb{N}^m$ is computable $\Leftrightarrow$ graph of function is Diophantine. Consider some subset $S$ of computable functions (for example some Grzegorczyk's class or ...
1
vote
0answers
180 views

what are the advantages and disadvantages of Belief propagation

Belief Propagation cannot solve the graphical model which has cycles. For undirected graphical model for example MRF and CRF in computer vision area, in which cases the model has no cycle ? As far as ...
0
votes
1answer
43 views

classifying problems with reducibility

How can we use a reduction to prove non membership of a class. Can we say if A is reducible to B they are in same class or if we can't reduce A to B. B is not same class as A. Regards,
2
votes
1answer
75 views

Group of computable permutations

Why group of computable permutations of natural numbers is not finitely generated? It is obvious for all permutations but why it is also true for computable permutations?
1
vote
1answer
53 views

Logic question- its about propositional logic and it asks for a valuation for statisfiability

I dont understand this question that comes from a past paper, so please any help is appreciated. The part that i dont understand is what does it mean (question 3) that it wants me to consider the ...
3
votes
2answers
123 views

Need Help to convert a grammar into Chomsky Form

I have to convert the following grammar into Chomsky Form $$( \Sigma=\{a,b,c,+\}, \Sigma_Q=\{S,V\},I=S)$$ $$S -> S+S|V$$ $$V -> a|b|c$$ My idea is the following: $$S_0 \rightarrow S$$ $$S ...
0
votes
2answers
176 views

110 people divided into 3 groups of different sizes

I need to distribute 110 people to 3 groups of different sizes as follows: 50 people to group 1 40 people to group 2 20 people to group 3 Instead of simply filling each group up to the desired size ...
1
vote
2answers
37 views

binary representation shrinkage question

Suppose for a given number $n$, every operation is to add $+$ signs arbitrarily into its binary representation. Repeat this process $K$ times. Prove: It is always possible to reduce the number to ...
2
votes
2answers
88 views

Height at 2D coordinate on a 3D rectangular surface

The Problem: How can I obtain every 3D coordinate on a rectangular surface given x and z? For those who are visual, picture looking down on the surface, and finding the height at where the x and z ...
2
votes
1answer
55 views

Why do we need “alphabets” defined?

I'm reading over my computational theory book before quarter starts and it's giving me the following definitions. alphabet: any nonempty finite set symbols: members of the alphabet I ...
1
vote
2answers
56 views

Best way to generalize a distribution of data into smaller subsets?

Suppose I had a data set as follows: 168.95, 176.83, 178.13, 179.61, 179.44, 172.83, 173.37, 174.06, 174.94, 175.43, 175.73, 175.5, 173.78, 174.06, 172.71, 174.3, 178.38, 178.43, 177.18, 175.34, ...
0
votes
1answer
76 views

Help with probability formula in programming problem

I am trying to solve this dynamic programming problem using probabilities. I know how the recurrence for it should look but I have problems using a probability formula. I have the next case: In a ...
4
votes
1answer
99 views

Minimizing the distance between points in two sets

Given two sets $A, B\subset \mathbb{N}^2$, each with finite cardinality, what's the most efficient algorithm to compute $\min_{u\in A, v\in B}d(u, v)$ where $d(u,v)$ is the (Euclidean) distance ...
3
votes
1answer
63 views

Mapping reduction to show NeverHalt is undecidable

I need help with showing that $NeverHalt_{TM} = \{\langle M\rangle|M\text{ is a TM which runs forever on every input $w$}\}$ is undecidable by giving an explicit mapping reduction. To show that a ...
0
votes
1answer
57 views

How to prove such program is uncomputable

We say that two programs are equivalent if they give the same output on every input. Prove that it is impossible to write a computer program that takes as input two pieces of code, code1 and code2, ...
1
vote
1answer
83 views

Does proving that a function is not in big O mean that the function is in big Omega?

If I determine that a function is not in Big O of another function, can you assume that the function is in big Omega of the same function?
1
vote
2answers
164 views

Choosing Codes or sequences with excellent Auto-Correlation properties

The Auto-Correlation function of Walsh-Hadamard codewords does not have a good characteristics. It can have more than one peak and thus, the Walsh-Hadamard codes do not have the best spreading ...
1
vote
1answer
39 views

Tight bound on the worst running time

I have to find a tight bound for an algorithm. I ended up with $3n^2 + 5$ as the worst running time of the piece of code. Is it ok if I consider $n^2$ as the tight bound? $$3n^2 + 5 \in ...
1
vote
2answers
146 views

Probability that $\frac{n}{2}$ bins are empty [close]

A Bloom filter of length $n$ was built. I have only the first $\frac{n}{2}$ bits of this filter. How will the false positive probability change? For the whole Bloom filter, the false positive ...
0
votes
1answer
405 views

Calculating normals for a polygon mesh (3D computer graphics)

I want to write a program to generate arches, a common architectural form, and export them to a wavefront object format for sharing with various three dimensional graphics editors. To do this, I need ...
0
votes
1answer
21 views

proving regular language

let $L$ be a language over the alphabet $\{a,b\}$ that maintains that for each $w \in L$ ,the difference in absolute between the number of apearences of the letter $a$ and the number of apearences ...
0
votes
1answer
60 views

Regular expression-language

I want to draw the DFA of the language that is given of the following expression, but I got stuck... Let the expression be {$(xy)^{*},(zx)^{+}$}$xz$ . Could you help me understanding which language it ...
10
votes
1answer
194 views

Is it possible that P != NP cannot be proved?

I am probably asking a stupid question but what I gather from a layman explanation of Godel's incompleteness theorem is that it is completely possible that a true statement cannot be derived from ...
0
votes
1answer
33 views

first order definability with $<$ vs $Succ, 0$.

In first order logic formulae with just the predicate $<$ could describe more structures than first order formulaes with $Succ$ (successor predicate) and a constant $0$ such that $\forall x (\neg ...
2
votes
0answers
93 views

Cut-off Subtraction in Coq

I am new to the world of computer assistant proof programs in general, and Coq in particular. As a result, I have sought to prove some elementary results about integers as a way to … At the moment, I ...
1
vote
1answer
89 views

Is there a DFA with $k+2$ states which its reverse has $2^k$ states

I am trying to figure out if there exists a DFA $M$ with $k+2$ states (for every $k\in \mathbb{N}$ ) so that every automaton which accepts $L(M)^R$ has at least $2^k$ states. I am trying to find an ...
4
votes
2answers
240 views

How to understand the definition of sets in homotopy type theory and the role of univalence?

Bear with me, I'm a physicist. In homotopy type theory, as I understand it, a type $X$ is a set if all the morphisms over its terms $x:X$ are identies. When I say "morphisms", then I view the term as ...
2
votes
1answer
123 views

Finding aggregate score from incomplete data

$$ \begin{align} n & = \text{number of reviews}\\ x & = \text{review score}\\ \bar{x} & = \text{aggregate score} \end{align} $$ I have a specified number of reviews for a product, I have ...
1
vote
1answer
43 views

Prove the existence of $C\in L_{regular}$ so that: $A \prec C \prec B $

Given $A,B$ regular languages. Prove the existence of $C\in L_{regular}$ so that: $A \prec C \prec B $ Whereas $A\prec B$ stands for: $A\subset B $ and $B\setminus A $ is infinite regular language. I ...
0
votes
1answer
48 views

Communication complexity example problem

Let $G = (V,E)$ and $H = (W,F)$ be two undirected graphs with $|V| = |W| = n$. G and H are isomorphic if there is a bijection f : V -> W such that: $\{u,v\} \in E$ <=> $\{f(u),f(v)\} \in F$ ...
2
votes
1answer
49 views

Proving that $L=\{w\in \Sigma^*: |w|_a= 2^n +273$, $n\in \mathbb{N} \}$ is irregular. [duplicate]

I am trying to prove that $L=\{w\in \Sigma^*: |w|_a= 2^n +273$, $n\in \mathbb{N} \}$ is irregular, whereas: $\Sigma=\{a,b\}$. I tried to use the pumping lemma with no success. I have also tried to ...
4
votes
2answers
268 views

NP-complete: One proof to rule them all

To prove a decision problem $C$ is in NP-complete, 2 things need to be shown: There is a polynomial verification for $C$ solution. Every problem in NP is reducible to $C$ - You can solve all the ...
1
vote
3answers
357 views

Context free grammar question

i have two context free grammar questions and I don't know how to do them. $$\{(a^n)b(c^n) \mid n >0 \}$$ I'm having trouble with this one because I don't know how to account for $a$ or $b$ not ...
1
vote
1answer
440 views

Time complexity of binary sum

What is the time complexity of binary sum, the sum of two binary numbers done like in elementary school? Say one number is F and his length is $s$ bits, and another number is H and his length is $t$. ...