Questions which also contain a proof or a solution that needs to be checked for correctness and completeness.
1
vote
1answer
51 views
How can I show a linear languages are closed against concatenating with regular ones?
This was given as a homework problem but I have already submitted the assignment. I'd like to resolve it at this point for my own satisfaction.
Given that $L_1$ is a linear language and $L_2$ is a ...
3
votes
1answer
42 views
Lower bound for sorting n arrays of size k each
Given $n$ arrays of size $k$ each, we want to show that at least $\Omega(nk \log k)$ comparisons are needed to sort all arrays (indepentent of each other).
My proof is a simple modification of the ...
0
votes
0answers
26 views
0
votes
0answers
157 views
Proof that P != NP (proof-check) [closed]
A proof that P != NP.
Warning: This proof uses descriptive complexity. I would post it on cstheory.stackexchange.com , but they don't want P vs. NP proofs.
The argument that P != NP is ...
2
votes
3answers
359 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 ...
8
votes
1answer
74 views
Number of Hamiltonian cycles on a Sierpiński graph
I am new to this forum and just a physicist who does this to keep his brain in shape, so please show grace if I do not use the most elegant language. Also please leave a comment, if you think other ...
1
vote
1answer
59 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}
...
2
votes
1answer
56 views
Prove $\varphi(x)$ to be primitive recursive
Let $\varphi(x)=2x$ if $x$ is a perfect square, $\varphi(x) = 2x+1$ otherwise. Show $\varphi$ is primitive recursive.
In proving $\varphi$ to be a p.r. function I think it could come in handy the ...
3
votes
2answers
128 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 ...
6
votes
1answer
134 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 ...
1
vote
1answer
110 views
How to prove transitivity in small-o of asymptotic analysis?
Here is my proof, but I am not sure whether it is correct.
We know:
$\qquad \begin{array}{l}
\forall {c_1},\exists {n_1},0 \le f\left( n \right) \le {c_1}g\left( n \right),\forall n \ge {n_1} \\
...
1
vote
2answers
132 views
Proving $\Omega(cf) = \Omega(f)$
I'm trying to prove the following lemma:
$c$ is a positive real number and $f, g$ are functions from natural numbers to non-negative real numbers. I'm trying to prove rigorously that:
...
1
vote
1answer
90 views
Error in Generating Function Solution
I am currently working my way through An Introduction to Analysis of Algorithms to stay sharp with recurrences as well as learn generating function techniques. However my analyses and the books ...
5
votes
2answers
201 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 ...
1
vote
2answers
271 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$ ...
6
votes
1answer
183 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 ...
6
votes
1answer
121 views
Proving NP is a subset of the union of exponential DTIME
I need to prove that $\mathsf{NP}$ is a subset of the union of $\mathsf{DTIME}(2^{n^c})$ for all $c > 1$.
Let $L$ be a language/decision problem in $\mathsf{NP}$. Then $L$ can be decided given a ...
9
votes
1answer
320 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 ...
