# Tagged Questions

33 views

### Expected Value on code

I'm trying to figure out the expected number of times this algorithm will print. I'm stuck on how to go about doing so. I used an indicator variable to keep track of the number of print statements ...
54 views

### What is the probability the best case occurs? (Comp Sci Type Question)

I'm having trouble figuring out what's the probability the best case occurs? It's my first time bringing together probabilistic knowledge into computer science. The question goes as such. Consider ...
33 views

### Language of a grammar vs regular expression vs nfa

I read some note about Automaton Course. i see this note, that following all is the same. but i think the L(g) is not equal to NFA and regular expression. anyone could help me with defining the ...
85 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 ...
23 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})$?
31 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$ ...
48 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 ...
13 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 ...
175 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 ...
44 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 ...
22 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?
138 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 ...
90 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 ...
19 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 ...
26 views

36 views

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

Why aren't there any languages in P that are not P-complete?