Questions tagged [check-my-answer]
Questions asking us to check whether your solution is correct are considered off-topic (per http://meta.cs.stackexchange.com/questions/597/) and should not be posted on this site.
15
questions
14
votes
5answers
6k views
Flaw in my NP = CoNP Proof?
I have this very simple "proof" for NP = CoNP and I think I did something wrongly somewhere, but I cannot find what is wrong. Can someone help me out?
Let A be some problem in NP, and let M be the ...
2
votes
1answer
2k views
Context Free Grammar for language L
Can someone help with this:
$L=\{a^ib^j \mid i,j \ge 1 \text{ and } i \ne j \text{ and } i<2j\}$
I'm trying to write a grammar for this language?
I tried this:
$S \to S_1 \mid S_2 \\
S_1 \to aXb ...
6
votes
1answer
854 views
Generalizing the Comparison Sorting Lower Bound Proof
Let's start with the comparison sorting lower bound proof, which I'll summarize as follows:
For $n$ distinct numbers, there are $n!$ possible orderings.
There is only one correct sorted sequence of ...
13
votes
2answers
2k views
Is Karp Reduction identical to Levin Reduction
Definition: Karp Reduction
A language $A$ is Karp reducible to a language $B$ if there is a polynomial-time computable function $f:\{0,1\}^*\rightarrow\{0,1\}^*$ such that for every $x$, $x\in A$ if ...
0
votes
2answers
3k views
Are supersets of non-regular languages also non-regular?
I have to proof that if $L_1 \subset L_2$ and $L_1$ is not regular then $L_2$ it not regular. This is my proof. Is it valid?
Since $L_1$ is not regular, there does not exists a finite automata $M_1$ ...
3
votes
2answers
2k views
Show $x^y$ is a primitive recursive function
As this thread title gives away I need to prove $x^y$ to be a primitive recursive function.
So mathematically speaking, I think the following are the recursion equations, well aware that I am ...
11
votes
1answer
3k views
subsets of infinite recursive sets
A recent exam question went as follows:
$A$ is an infinite recursively enumerable set. Prove that $A$ has an infinite recursive subset.
Let $C$ be an infinite recursive subset of $A$. Must $C$ ...
2
votes
1answer
905 views
Prim's algorithm: difference between brute force and PQ approaches
I'm trying to figure out the different way we obtain an MST with a brute force Prim's algorithm compared to the optimized version based on priority queues.
Given a graph $G=(V,E)$, the former can be ...
2
votes
2answers
205 views
Find an upper bound for $T(n)=T(\sqrt{n})+10\log\log n$
I need to find an upper bound for $T(n)=T(\sqrt{n})+10\log\log n$.
I thought first to make a substitution: $m=\log n$. Then:
$$
T(2^m)=T(2^{m \over 2})+10\log m
$$
Let $S(m)=T(2^m)$:
$$
S(m)=S\big({m ...
1
vote
1answer
356 views
Let M be an $\epsilon$-NFA and let $S\subseteq Q$. Prove $\epsilon (S) = \epsilon (\epsilon (S))$
Let M be an $\epsilon$-NFA and let $S\subseteq Q$. Prove $\epsilon (S)= \epsilon (\epsilon (S))$.
I would like to prove this by contradiction but I don't know if my idea is correct.
Definition of $...
1
vote
1answer
3k views
Every AVL tree may be red black tree
I proved by induction that every AVL tree may be colored such that it will be red black tree. The problem is that I can't see an error in my proof. Look at my proof.
Induction for height.
Let's ...
6
votes
1answer
347 views
What is the complexity of this subset merge algorithm?
Updated Algorithm: There was a major flaw in my original presentation of the algorithm which could have impacted the results. I apologize for the same. The correction has been posted underneath.
The ...
6
votes
1answer
446 views
Show that the halting problem is decidable for one-pass Turing machines
$L=\{<\!M,x\!>\, \mid M's \text{ transition function can only move right and } M\text{ halts on } x \}$. I need to show that $L$ is recursive/decidable.
I thought of checking the encoding of $...
1
vote
1answer
401 views
Show $H_1(x)$ is partially computable
I need to show that $H_1(x)$ defined as follows is partially computable.
\begin{equation}
H_1(x)=
\begin{cases}
1 \;\;\;\;\;\text{ if } \Phi(x,x) \downarrow \\
\uparrow \;\;\;\;\; \text{ otherwise}
\...
0
votes
1answer
136 views
Minimal paths as solution of a linear program of a special network flow
Let $G= (V,E)$ be a given directed weighted graph, and $s,t$ two specified nodes, so that there is no negative cycle reachable from $s$, and $t$ is reachable from $s$.
We're looking for the shortest ...
