Problem Detail: I am looking for an algorithm with time complexity in $mathcal O(|V|)$ that determines whether a given graph $G=(V,E)$ is a caterpillar tree. A caterpillar tree is a tree that has a path to which all nodes are connected Read More …
Blog
[Solved]: Prove or refute: BPP(0.90,0.95) = BPP
Problem Detail: I’d really like your help with the proving or refuting the following claim: $BPP(0.90,0.95)=BPP$. In computational complexity theory, BPP, which stands for bounded-error probabilistic polynomial time is the class of decision problems solvable by a probabilistic Turing machine in Read More …
[Solved]: Proving Linear Time Temporal Logic formula □ ◊ f ⇔ ◊ □ f
Problem Detail: I am new to this topic, Linear Time Temporal Logic and I am trying to prove this equivalence — $BoxDiamond f Leftrightarrow DiamondBox f$ This is my take — Basic definitions: $(sigma, j) models Box f: forall k , Read More …
[Solved]: pda: transformation between acceptance by empty stack and final states
Problem Detail: I am stuck with understanding the transformation of final-state acceptance automaton into empty-stack acceptance automaton. From everywhere that I’ve read, it always says introduce a new start state with a new start stack symbol, and another state after the Read More …
[Solved]: Can every state in a DFA be an accepting state?
Problem Detail: I know that we can have 0 accepting states in a DFA, it would just recognize the empty language. What about the case of all states being accepting? Would that mean it would recognize all of the strings in Read More …
[Solved]: Kleene star operation on the empty language
Problem Detail: In my text book it is mentioned that: $emptyset^*={epsilon}$ where $emptyset$ is an empty language. However, we know that $L cdot emptyset = emptyset$, where $L$ is any Language. I am not able to intuitively grasp this concept because Read More …
[Solved]: Is regularity of the language accepted by a given Turing machine a semi-decidable property?
Problem Detail: Given is the definition of a general problem: ${ langle M, Srangle mid M text{ is a } TM, L_M in S}$. In words: Given a TM M, does M decide a language that is an element of the Read More …
[Solved]: Kolmogorov Complexity: Why would you need more bytes than the string itself?
Problem Detail: I was reading Wikipedia’s entry on Kolmogorov Complexity (thanks to this question), which states: It can be shown that the Kolmogorov complexity of any string cannot be more than a few bytes larger than the length of the string Read More …
[Solved]: Traveling Salesman’s Tour Approx Algorithm: is this really a Hamiltonian Path?
Problem Detail: I’m given this problem: Consider the following closest-point heuristic for building an approximate traveling-salesman tour. Begin with a trivial cycle consisting of a single arbitrarily chosen vertex. At each step, identify the vertex u that is not on the Read More …
[Solved]: How to prove that the pre-order tree traversal algorithm terminates?
Problem Detail: I see structural induction the usual way for proving an algorithm’s termination property, but it’s not that easy to prove by means of induction on a tree algorithm. Now I am struggling on proving that the pre-order tree traversal Read More …
