Category: Uncategorized

Problem Detail: I am interested in the following version of TSP: Assumption: TSP where the distances are non-negative. We know the algorithm A which computes the optional solution for such instances of TSP. Task: State an algorithm that uses the algorithm Read More …

Problem Detail: $L = {0^i1^j0^i1^j|i,j geq 0}$ I’ve tried letting $s = 0^p1^p0^p1^p$. But not sure where to go from here. Help would be appreciated. Asked By : user678392 Answered By : Patrick87 Take a look at the following proof; if this is Read More …

Problem Detail: It’s probably possible to prove that P ≠ NP, that one-way functions exist, and that parity games cannot be solved in polynomial time (yes, I’ve been reading through this list), but how would we go about proving any of Read More …

Problem Detail: I already read this related question on the intuition behind binary indexed trees, and while the answer explains how the tree structure works, it does not really explain how this correlates back to the array representation where the next Read More …

Problem Detail: We say that the language $J subseteq Sigma^{*}$ is dense if there exists a polynomial $p$ such that $$ |J^c cap Sigma^n| leq p(n)$$ for all $n in mathbb{N}.$ In other words, for any given lenght $n$ there exist Read More …

Problem Detail: My question is the following: How to calculate the regret in practice? I am trying to implement the regret matching algorithm but I do not understand how to do it. First, I have $n$ players with the joint action Read More …

Problem Detail: In the book introduction to automata theory and languages, $L^*$ is defined as $$L^* = bigcup_{i=0}^infty L^i $$ The book also says that $emptyset^* = { epsilon }$. But since $emptyset$ is the empty set $$L^* = L^0 cup Read More …

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 …

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 …

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 …