Problem Detail: I am reducing a given Turing Machine to the complement of the known undecidable problem, $$ Complement(A_{TM}) = { langle M,w rangle mid M text{ is TM}, w notin L(M) }$$ To this Turing Machine, known as SPARSE TM: Read More …
Category: Uncategorized
[Solved]: Unambiguity of Reverse Polish Notation
Problem Detail: Lets say I have given following grammar which generates arithmetic expressions in reverse polish notation: $G=({E},{a,+,*},P,E)$ $P={ E rightarrow EE+ | EE* | a }$ I know this grammar is unambiguous. What I do not understand is how I Read More …
[Solved]: Reduce variant of Vertex Cover to original decision-version Vertex cover problem
Problem Detail: Consider the following variation (let us call it Q) on the Vertex Cover problem: Given a Graph G and a number K, we are asked if there is a k-cover of G so that it is the minimum cover. Read More …
[Solved]: Turing machine with repeated strings
Problem Detail: How would I go about making a Turing machine to accept the following language L? $$L = { www mid w = {0,1}^* text{ and } w > 0}$$ I was thinking counting the number of symbols in the Read More …
[Solved]: Finding undirected cycles in linear time (triangulating graphs while minimizing degree)
Problem Detail: In the article [“Triangulating Planar Graphs While Minimizing the Maximum Degree”] by Kant and Bodlaender [1], Section 4 briefly mentions the extraction of elementary cycles (no repeating edges) from what I assume is an undirected graph $H$. It has the following Read More …
[Solved]: Does there exist a proof of closure of regular languages under regular substitution by giving the corresponding DFA?
Problem Detail: Every proof I can find of this result is by way of regular expressions. Is there any “constructive” proof that defines the corresponding DFA (probably NFA)? For instance the proof of concatenation closure is most often presented by demonstrating Read More …
[Solved]: Saving on array initialization
Problem Detail: I recently read that it is possible to have arrays which need not be initialized, i.e. it is possible to use them without having to spend any time trying to set each member to the default value. i.e. you Read More …
[Solved]: An obvious approach to explaining NP != coNP, how far has it been pushed?
Problem Detail: A recent question made me think about an obvious approach for circumventing the “algorithm is allowed to do anything” problem, when proving lower bounds. Instead of starting with a simple looking NP-complete problem, start with a powerful looking logical Read More …
[Solved]: What is a clairvoyant algorithm?
Problem Detail: When talking about general data structure design, my lecture notes talk about one of the concerns being cost of operations. As well as the individual cost, it mentions amortized cost. But then it goes on to say: Amortized cost Read More …
[Solved]: How to recognize a STRIPS planning problem has no solution?
Problem Detail: Strips –Stands for STanford Research Institute Problem Solver (1971). STRIPS Pseudo code – STRIPS(stateListstart, stateListgoals) 1.Set state = start 2.Set plan = [] 3.Set stack = goals 4.while stack is not empty do 1.STRIPS-Step() 5.Return plan STRIPS-Step() switch Read More …
