# Tagged Questions

69 views

### SQRTSORT from Vazirani's book on algorithms

I study the Algorithm book and saw the following exercise. I couldn't solve it. This is not homework, nor exam. Just reading some material on algorithms for preparing entrance exam. Any nice idea or ...
21 views

### Omega Notation and Average Running Time Problem

if we have an algorithm that average running time of randomized algorithm A for input of size n is equal to $\theta(n^2)$. why there would be an input data such that A solve it in $\Omega(n^{3n})$?
29 views

### Pushdown Automata and Challenge in Grammar

I read one old-midterm exam on Automata. consider: the language that accepted by above pushdown automata is not generated by which of the following grammar? 1) S->aBaa|a$\epsilon$ ...
43 views

### Regular Language and Unknown Operation

I read the $L$ is a Regular language. Define $L'$ as following: $$L'=\{a_2a_1a_4a_3\ldots a_{2n}a_{2n-1}\mid a_1a_2\ldots a_{2n} \in L\}.$$ why $L'$ is Regular? any hint or idea would be highly ...
10 views

### Can this language be solved in PTIME?

I would like to know why we cannot prove that $P \subsetneq PSPACE$ by considering the following language for some particular Turing Machine $M$: $L_M:=$ {$w : M$ accepts or rejects $w$ without using ...
169 views

### The mother of all undecidable problems

It is usual to show that a problem P is undecidable by showing that the halting problem reduces to P. Is it the case that the halting problem is the mother of all undecidable problems in the sense ...
42 views

### predicate logic with assumption NP $\neq$ CO-NP?

Anyone could describe why: Set of All Tautology in propositional logic with assumption NP $\neq$ CO-NP is CO-NP Complete. Thanks. I ask it here before: Is the language of tautologies NP-complete? ...
55 views

### Computable Set & Function

we know that i read this sentence are true? can anyone say an example for following sentence? there are a non computable set A such that
63 views

### TAUTOLOGIES NP-Complete Condition

The decision problem TAUTOLOGIES is, Given $\forall x_1 \forall x_2 ... \forall x_n$ $\phi(x_1, x_2, ... x_n)$ a set of universally quantified Boolean variables and a Boolean formula ...
46 views

### Recursive Set and Complement Problem

if we have $$A=\{x:|W_x\ne\phi\}$$ can we say always my tight listed below is true? $A$ is recursive , $A$ is r.e, complement of $A$ is r.e, complement of $A$ is not recursive?
27 views

### Using the pumping lemma to prove that a certain language is not regular

I've been trying to understand the pumping lemma since forever, I just don't know what it does, I have no clue what any of it does. My college professor sucks, he thinks writing a bunch of stuff on a ...
21 views

### Reduction between languages in P

I have a simple question about the class P: Is there exist a polynomial time reduction between every two languages A, B in P?
92 views

### Calculating time complexity of algorithms written in pseudocode.

Nowadays we are interested to find some algorithms with a prescribed running time. For example if for certain decisional problem $X$ there is an algorithm with running time $O(n^3)$ we try to break ...
89 views

### Questions about a computer science field

I would like to have some information about the computer science field, " Algorithmic and Systems Analysis ". Is this a field of theoretical computer science? What subjects are related with this ...
25 views

34 views

### Natural Decision Problem not in PTIME

Are there any natural decision problems which are guaranteed not to be in $\mathsf{PTIME}$? Preferably natural graph problems like $\mathsf{CLIQUE}, \mathsf{VERTEXCOVER}$ etc. (However, they would be ...
17 views

### Reduction of halting problem

I can show that this reduction !H â‰¤ H where H is the general halting problem an !H is the complement of it. But what with H â‰¤ !H ...
25 views

36 views

### Languages in P that are not P-complete

Why aren't there any languages in P that are not P-complete?
40 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 ...
53 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 ...
34 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$ ...
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 ...
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$. ...