G. Bach
  • Member for 8 years, 11 months
  • Last seen more than a week ago
Matrix Max in less than O(n)
Accepted answer
15 votes

If you don't know anything about the contents of the matrix (such as some kind of monotonicity property), linear time is the best you can do for a one-off search with a deterministic algorithm by a ...

View answer
What's Big O of $\log(n+7)^{\log(n)}$?
Accepted answer
11 votes

If you meant what $\mathcal{O}((\log (n+7))^{\log (n)})$ is (so the power applies to the logarithm itself, not its argument), then we simplify that to $\mathcal{O}((\log (n))^{\log (n)})$; as per a ...

View answer
Can you solve 2-sat problem when truth assignments of some variables are determined
Accepted answer
9 votes

First set all literals $x$ to $1$ if they appear in a clause $0 \vee x$, and set $\bar x$ to $0$. If that requires you to set some $x$ to both $0$ and $1$, it's unsatisfiable. Iterate this until you ...

View answer
Are all minimum spanning trees optimized for fairness?
Accepted answer
8 votes

is it possible to have two MSTs in a graph (equal global sum of their edges) but have one of those MSTs contain an edge of higher value than any edge on the other MST in the graph. No, it isn't; ...

View answer
If set membership problem can be solved for a particular language does this imply that the language is regular?
7 votes

Since any irregular, but decidable language answers the question with "no, there are irregular languages that are decidable", maybe some nuance for how this relates to the usual complexity classes. ...

View answer
How to implement two stacks in one array?
7 votes

Another hint in addition to what Yuval said: it helps to place the stacks in a specific way in the arrays and fix their direction of growth accordingly. They don't have to grow in the same direction.

View answer
How do computers compute?
6 votes

I'm not entirely sure if I understood the question the way it was intended, but what computers do is that they operate on electricity, so they don't have two discrete logical values $0$ and $1$ per se....

View answer
does a DFA converted from NFA always contain 2^Q states?
Accepted answer
6 votes

As per suggestion, I'm posting this as an answer. Any DFA already is an NFA. Determinizing it will not change the number of states it has, so there are NFA that do not have fewer states than the ...

View answer
Does coNP-completeness imply NP-hardness?
6 votes

The problem with that line of reasoning is the first step. In the deterministic case, you can decide $x \in L$ with a TM $\text{M}$ iff you can decide $x \notin \overline{L}$ with it, because the way ...

View answer
Why is the set of all regular expressions classified as context-free, instead of regular?
4 votes

The regular languages are closed under finitely many applications of choice, star, concatenation. If you allowed infinitely many applications, every language would be regular since every language $L$ ...

View answer
Questions on the definition of polynomial time
4 votes

Note that the questions you're asking (apart from 3.) don't have anything to do with complexity theory, so you'll have to forget that mindset for a moment to understand what you read. Because ...

View answer
Proving Little-Oh notation by definition
4 votes

Either you do what David suggested, or you do something like this: Let $c > 0$. Then \begin{align} 5n^2 +3n &\le c(n^3-4n) &\iff \\ 5n+3 &\le cn^2-4c &\iff \\ 0 &\le cn^2-5n-(...

View answer
Solution for a combinatorial minimization problem
4 votes

For any $a$ we have $\text{max}\,\{\binom{a}{b}\} = \binom{a}{\lceil a/2 \rceil}$ since the binomial grows towards "the middle" and afterwards declines again (a proof for that is not difficult and ...

View answer
Distributivity of $\omega$-regular expressions
4 votes

As suggested by Raphael, here's a proof doing it via the sets represented by those expressions. $\qquad L_\omega((E_1+E_2) \cdot F^\omega) \\= L(E_1+E_2) \cdot L_\omega(F^\omega) \\= (L(E_1) \cup L(...

View answer
When is the output of shortest path $\subset$ MST?
Accepted answer
3 votes

A basic observation first: in any unweighted graph with a cycle, there is an MST that is not a shortest path tree for some source node. Proof: the tree must omit some edge on the cycle, and for either ...

View answer
Is there a name/algorithm for this problem related to set cover and CSP?
3 votes

Just to be sure, I assume that $\mathcal{G}^* = 2^\mathcal{G}$, i.e. that $\mathcal{G}^*$ is the power set of $\mathcal{G}$. Alright, we can use the following flow network $(V,E,\text{cap})$: let $V =...

View answer
Basics of Amortised Analysis
3 votes

I'll just answer a) and b) because I don't know the potential method. About a) Worst case analysis only considers a single operation. If you want to know how expensive your algorithm is in its worst ...

View answer
Sort edges in euclidean graph
Accepted answer
3 votes

If you find a way to do this, then you can build a sorting algorithm that does it faster than the $\Omega(n \log n)$ boundary on comparison sort. How you would build the sorting algorithm: let the ...

View answer
Efficiently pick a largest set of non-intersecting line segments
2 votes

EDIT: Falk Hüffner gave a reduction in his comment to the question, the problem is in fact NP hard. What follows is pretty useless for that reason. I'll leave it up anyway so the answer doesn't look ...

View answer
Lines intersections with a point in 1D
Accepted answer
2 votes

You can do the trivial scan in $\mathcal{O}(n)$ time where $n$ is the number of intervals (just check for each interval whether your value is in it) or you can use an interval tree; those allow for ...

View answer
Converting graphs to sets of paths
2 votes

This should be NP-hard, here's a way you could try to do a reduction: Take any graph $G$ embedded in the $\mathbb{R}^2$ plane. Let $c_{min} = \min_{e \in E}\{c(e)\}$ be the minimum edge weight in ...

View answer
Are turing machine really countable?
2 votes

Maybe a more straightforward illustration of the "up to isomorphism" thing: take a TM with 1 state and no transitions, then you can generate uncountably many TMs by assigning the state some subset of $...

View answer
A graph in descriptive complexity - is $x$ already a vertex?
1 votes

(First-order logic) formulae are independent of structures; you just have variables, predicates and possibly functions (in addition to the syntactical symbols). To decide whether a formula $\varphi$ ...

View answer
Regex for the language over $\{a,b,c\}$ that contain at least two $a$'s but no two consecutive $b$'s
Accepted answer
1 votes

You'll need to guarantee the following: at some place, you have $aa$ whenever there is a $b$, then there is a different letter between it and any further $b$ So one part of your regular expression ...

View answer