Problem Detail: I read several times that it is not possible to flip the answer of a NDTM efficiently. However, I don’t understand why. For instance, given a NDTM $M$ that runs in $O(n)$, this text (section 3.3) states that it Read More …
Author: ignougroup
[Solved]: Can the heaviest edge ever be in an MST?
Problem Detail: Is it true that the heaviest edge in a directed graph can not be in the MST of that graph? I don’t think it is true because we might end up with a heaviest edge that is not part Read More …
[Solved]: Create CFG and pushdown automaton for {ww}
Problem Detail: I’ve been trying to make a CFG, a pushdown automaton and a regular expression for the language $qquad L(M) = {ww : w in {a, b}^*, |w| text{ is even}}$. I understand how the reverse of the string work, Read More …
[Solved]: Minimal DFA that accepts binary strings whose decimal equivalent is divisible by 32
Problem Detail: I thought the answer would be 32 for remainder $0,1,2,dots, 31$. But answer given as $6$. and explanation is given as if the number is $2^n$ then number of states required would be $n+1$. Asked By : Vikrant Answered By : David Read More …
[Solved]: Understanding proof for Busy Beaver being uncomputable
Problem Detail: I found this proof on http://jeremykun.com/2012/02/08/busy-beavers-and-the-quest-for-big-numbers/ and have highlighted the part I don’t understand in bold. (BB(n) is defined as the number of steps made by n-state Busy Beavers.) Theorem: BB(n) is uncomputable. That is, there is no Turing Read More …
[Solved]: number of subsets where GCD equals to X
Problem Detail: The original statement for this problem can be found here This is a question from IEEExtream 2014. There is an array of integers given. Input is X, so output is the number of subsets where there GCD equals to Read More …
[Solved]: XOR-like behavior in flow networks
Problem Detail: XOR is not the correct name, but I am looking for some kind of exclusive behavior. I am currently solving a set of different (assignment) problems by modeling flow networks and running a min-cost-max-flow algorithm. Flow networks are quite Read More …
[Solved]: Matrix Max in less than O(n)
Problem Detail: I am attempting to find the maximum value in a matrix (or 2d array) and want to find it in less than O(n) time. The easiest way, which results in O(n) run time, is an element wise search. If Read More …
[Solved]: If L1 ∪ L2 and L1 are regular, is L2 also regular?
Problem Detail: This is a problem in a theory of computation book that’s stumping me: Suppose that we know that $L_1 ∪ L_2$ and $L_1$ are regular. Can we conclude that $L_2$ is regular? Explain. At first, I thought I could Read More …
[Solved]: Where am I wrong?: “countability” and “recursive enumerability”
Problem Detail: I have a a few fundamental doubts in recursive enumerability and countability and below, I have written what I understand them to be with proofs. But there are contradictions at the end. What is wrong with the statements/proofs i Read More …
