New answers tagged

1

To show that the problem is in NL: guess a directed edge $(u,v)$ of the graph that is part of a cycle, and check (using the connectivity algorithm as a black-box, or by guessing each step of a walk) whether $v$ is connected to $u$ in $G$. To show that the problem is NL-Hard create a new graph $G'$ as follows: For each vertex $v$ of $G$ add $n$ vertices $v^...


0

Briefly, you create $n$ copies $(v,1),\ldots,(v,n)$ of each vertex $v$, adding an edge $(a,i)\to(b,i+1)$ for every original edge $a\to b$. So far the graph is a DAG. Now you add edges $(t,i)\to(s,0)$ for all $i$. I'll let you figure out why that works.


4

Initialize a counter at zero. Whenever you see "(", increase it by one, and whenever you see ")", decrease it by one. Accept if the counter was always nonnegative and ended up at zero. The counter only takes logarithmic space to store.


2

This amounts to reading the input string and keeping track of the difference $\delta$ between the number of open and closed parenthesis. If $\delta$ ever becomes negative, then the input is not properly balanced (at some point there is one more closed parenthesis than open ones). Similarly, if $\delta >0$ at the end of the string, then there are unclosed ...


0

I like this one: given a string $S$, find the longest substring that appears two or more times in $S$. There are plausible algorithms with running time $O(n^3)$, $O(n^2)$, $O(nk \log n)$, $O(nk \log k)$, $O(nk)$, $O(n \log n)$, $O(n \log k)$, and even $O(n)$, where $n$ is the length of $S$ and $k$ is the length of the longest such substring. However I don'...


3

The complexity class $\Sigma_2^P$, which is the second level of the polynomial hierarchy, consists of all languages $L$ for which there exists a polytime predicate $f$ and a polynomial $p$ such that $$ x \in L \Longleftrightarrow \exists y \forall z \, f(x,y,z), \text{ where } |y|,|z| \leq p(|x|). $$ This is the natural location for your problem: $x$ is a ...


3

The brute force solution enumerates all permutations. You can easily encode each permutation using $n\log n$ bits, since you can encode it as a list of numbers from $1$ to $n$, and each number takes $\log n$ bits to encode. You can check that a given permutation corresponds to a tour using $O(\log n)$ additional bits of space, so in total the space ...


Top 50 recent answers are included