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 ...

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 ...

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 ...

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; ...

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. ...

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.

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....

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 ...

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 ...

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$ ...

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 ...

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-(...

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 ...

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 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 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 =...

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 ...

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 ...

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 ...

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 ...

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 ...
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 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 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 ...