Problem Detail: In the book on complexity by Arora and Barak, there is an exercise to show $Space(n)neq NP$, the proof of which goes by showing that $NP$ is closed under Karp reductions, while $Space(n)$ isn’t. To show that $Space(n)$ isn’t Read More …
Category: Uncategorized
[Solved]: Relationship of algorithm complexity and automata class
Problem Detail: I have been unable to find a graph depicting or text answering the following question: Is there a direct relationship between the complexity of an algorithm (such as best / worst case of quick sort), and class of automata Read More …
[Solved]: Visualization of Lamport’s three-dimensional “space-time diagram” with introduced “tick lines”
Problem Detail: In the third page (the third paragraph in the right column) of the paper “Time, Clocks, and the Ordering of Events in a Distributed System” by Leslie Lamport, it says that The reader may find it helpful to visualize Read More …
[Solved]: Mapping reducibility vs. Turing reducibility
Problem Detail: Let $A$ and $B$ be two languages. If $A le_{m} B$ ( reducible by mapping ) then I know that if $B$ is decidable so is $A$ and if $B$ is recognizable so is $A$. And if $A le_{T} Read More …
[Solved]: No need to rename a free variable in substitution?
Problem Detail: I wonder if the following two substitutions are correct: $$(x,y)[x:=y] = (y,y)$$ $$ lambda y. (x,y) [x:=y] = lambda z.(y,z)$$ They are what I understand from http://en.wikipedia.org/wiki/Lambda_calculus#Substitution. Although I can follow the rules there mechanically, I wonder why there Read More …
[Solved]: Question about the formal proof of the inorder traversing
Problem Detail: In Don Knuth’s famous series of books, The Art of Computer Programming, section 2.3.1, he describes an algorithm to traverse binary tree in inorder, making use of an auxiliary stack: T1 [Initialize.] Set stack $rm A$ empty and set Read More …
[Solved]: Attack on hash functions that do not satisfy the one-way property
Problem Detail: I am revising for a computer security course and I am stuck on one of the past questions. Here is it: Alice ($A$) wants to send a short message $M$ to Bob ($B$) using a shared secret $S_{ab}$ to Read More …
[Solved]: NP Completeness of 3-SAT problem
Problem Detail: I have started reading on algorithmic complexity for my thesis work. Already have studied on Polynomial time reducibility, NP-Complete, NP-Hard. Now trying to prove NP completeness of some of the classical problems. I have started with 3-SAT problem. 3-SAT Read More …
[Solved]: Equivalence of two context free grammars [for the given example]
Problem Detail: I know that in general it is undecidable whether two context free grammars generate the same language, but I have to do this exercise and I am finding myself somewhat stuck: G1: S->e|aB|bA B->bS|aBB A->aS|bAA G2: S->e|aSb|bSa|SS I tried Read More …
[Solved]: Is it possible to always construct a hamiltonian path on a tournament graph by sorting?
Problem Detail: Is it possible to always construct a hamiltonian path on a tournament graph $G=(V,E)$ by sorting (using any sorting algorithm) with the following total order: $qquad displaystyle a leq b iff (a,b) in E lor left(exists, c in V. Read More …
