2
votes
1answer
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$ ...
0
votes
0answers
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 ...
9
votes
2answers
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 ...
1
vote
1answer
72 views

$NP^{PP} vs. PP^{NP}$, which one subsumes the other?

I understand why P with an NP oracle ($P^{NP}$) subsumes $NP$: because it contains co-NP. But how about NP with a P oracle? Can it be any different from NP? (I'm guessing they are the same otherwise ...
0
votes
0answers
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 ...
0
votes
0answers
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?
0
votes
0answers
11 views

Proof of theorem about connection between nondeterministic and deterministic Turing machines complexity classes

I need source for proof of this theorem: Every $T(n)$ time nondeterministic Turing machine has an equivalent $2^{O(T(n))}$ deterministic Turing machine. I have book by Michel Sipser, ...
1
vote
1answer
36 views

Languages in P that are not P-complete

Why aren't there any languages in P that are not P-complete?
2
votes
1answer
59 views

Prove that RE is closed under reduction

Prove that the class RE is closed under reduction. Definitions: A language $ A \subseteq \Sigma^*$ is called reducible to $ B \subseteq \Gamma^*$ ( denoted by $A \leq B$) if there is a computable ...
1
vote
0answers
64 views

Primitive recursive and Turing machines

Can someone give me a hint or the start of a possible proof for the following theorem: A function $f: \mathbb{N}^r \rightarrow \mathbb{N}$ is primitive recursive if and only if there is a ...
0
votes
1answer
46 views

Turing machines and tape complexity

Are the following statements true and/or false? There is a total function $g: \mathbb{N} \rightarrow \mathbb{N}$ so that for each Turing machine $M$ and each natural number $t$ we have: (*) ...
2
votes
1answer
110 views

Why do complex grammars require powerful algorithms?

I am reading a fabulous book on Formal Languages and in the book it says: As the rewrite rules of a grammar become more complex, the algorithm for recognizing the associated language becomes ...
2
votes
1answer
71 views

Unknown symbol '#' in set

I am reading a text on Complexity theory. There is a set whose notation I cannot understand: "Let $\sum$ = {0,1,#}" From the context, and given that the book is used computer science courses, it ...
0
votes
1answer
88 views

Simulating an alternating Turing Machine

I'm trying to figure out this question: Let's say we have an alternating Turing Machine that makes a restricted number of alternations (i.e. switches from a universal to an existential state or vice ...
2
votes
1answer
450 views

Baker-Gill-Solovay theorem

I have been trying to understand the proof of Baker-Gill-Solovay theorem as described in Complexity Theory: Modern Approach. I think I do understand most of it, but what troubles me is that let's say ...
1
vote
1answer
144 views

Understanding of working of Turing Machine for $\{0^k1^k\}$

I try to learn Computation Complexity by Sipser's textbook "Introduction to the Theory of Computation". The problem is I have a lack in understanding how Turing Machine is working. Example from the ...