# Tagged Questions

Questions which also contain a proof or a solution that needs to be checked for correctness and completeness.

114 views

93 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 ...
130 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 ...
1k 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 ...
138 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 ...
135 views

### Show $H_1(x)$ is partially computable

I need to show that $H_1(x)$ defined as follows is partially computable. H_1(x)= \begin{cases} 1 \;\;\;\;\;\text{ if } \Phi(x,x) \downarrow \\ \uparrow \;\;\;\;\; \text{ otherwise} ...
102 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 ...
518 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 ...
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 ...