If you are allowed infinite states and transition functions, then even a DFA could solve the halting problem (and in fact, any language). In this case, the DFA/TM can basically have a state for each ...

Evaluating these Big-O constants in real life situations is nearly impossible. Each computer has different hardware, and the precise cost of each operation (or even of only a specific type of ...

My intuition for why the reverse topological order is necessary is that given a node $v$ in a strongly connected component $C$, if $v$'s finishing time (denoted in CLRS as $f(v)$) is maximal, than so ...

I don't consider myself knowledgable enough about logic to provide a complete answer myself, but I think the following two posts (1 from math.stackexchange, one from mathoverflow) contain some ...

I think you might be slightly confusing your definition for co$NP$. To show that a certain graph doesn't contain a Hamiltonian path, you need to show that all paths in it aren't Hamiltonian, and ...

Your complexity calculation is incorrect. If for each vertex you go over all of its out edges, in a directed graph you'd only get a $O(|V|+|E|)$ complexity and not $O(|V|*|E|)$. A complexity of $O(|V|*... View answer Accepted answer 2 votes When trying to come up with a grammer for this language, there are several things one must make sure every word generated by it satisfies, including: It starts with a double$p$Every addition of a$...

To expand on what blue-dino wrote, is it indeed impossible to make a general sorting algorithm with worst-case (or even average-case) complexity which is better than $O(n\log(n))$. In this case "...
You aren't exactly correct in your example because of the redundant negation of the $\leq$ sign. In the most general sense, we always have: $$\neg (x_1 \land x_2\land ...\land x_n)=(\neg x_1) \lor...\... View answer Accepted answer 1 votes To add to old's answer, saying a TM runs in O(1) means that the number of steps the TM makes cannot become infinitely large depending on the size of the input, and is always bounded by some constant.... View answer 1 votes To add a more concrete example to chi's answer, in the case of CFL's, think about the following infinite union:$$\bigcup_{i=1}^\infty\{0^i1^i2^i\} = \{0^n1^n 2^n|n>0\}$$which is a known example ... View answer Accepted answer 0 votes As Aspass.Jack wrote in the comments, let's first define L_3 to be the language where each a is followed by at least 2 b's, and L_4 to be the language where each b is followed by at least ... View answer Accepted answer 0 votes As Yuval commented, this is a very basic exercise so you should probably go over the basic definitions. One simple answer for this particular question is:$$S\rightarrow0S11|\varepsilon