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

learn more… | top users | synonyms

1
vote
0answers
114 views

Single machine job scheduling (Greedy heuristic)

Here is a variation of a job-scheduling Problem. Let $J = \{j_1,...j_n\}$ be a set of Jobs for $1 \leq i \leq n$. Given Job length $|j_i|\in \mathbb{N}$, deadline $f_i \in \mathbb{N}$, profit $p_i \ge ...
2
votes
2answers
71 views

Show $B= \{z \mid (\exists x)\; P(x,z)\}$ is a recursive enumerable set

Let $B = \{z \mid (\exists x)\; P(x,z)\}$ and $P$ be a computable predicate. Show $B$ is a recursive enumerable set. My attempt As $P$ is a computable predicate then there is a program that computes ...
5
votes
1answer
107 views

Proving that a language is not in P using diagonalization

Pardon me if i'm missing something which is very obvious here but i cant seem to figure it out. $E=\{ \langle M, w \rangle \mid \text{ Turing Machine encoded by $M$ accepts input $w$ after at most $ ...
4
votes
1answer
76 views

Quasigroups, congruences and recognizable subsets

My question refers to the draft of Mathematical Foundations of Automata Theory, IV.2.1 (pages 89ff in the pdf). I will repeat everything necessary nevertheless: Let $M,N$ be monoids and $\varphi: M ...
1
vote
1answer
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 ...
3
votes
1answer
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 ...
6
votes
3answers
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 ...
10
votes
1answer
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 ...
1
vote
1answer
135 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
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 ...
3
votes
2answers
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 ...
6
votes
1answer
270 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
240 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
141 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
99 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 ...
6
votes
2answers
350 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
447 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
231 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
163 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 ...
10
votes
1answer
604 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 ...