39 Example of a graph with negative weighed edges in which Dijkstra's algorithm does work 37 Time complexity $O(m+n)$ Vs $O(n)$ 28 How can a Turing machine compare two strings without modifying them? 13 Is an integer variable constant or logarithmic space? 10 Is there any NP-hard problem which was proven to be solved in polynomial time or at least close to polynomial time?

### Reputation (8,787)

 +35 Prove or disprove: $L^n=M^n\nRightarrow L=M$ where $L$ and $M$ are languages +10 Polynomial time optimization problems belong to which complexity class? +45 What is the meaning of the pipe symbol here? +10 What is the regular expression for the language, {w | w does not contain the substring 11}

### Questions (20)

 4 Combinatorics - how many $c$-distinct sets are possible? 4 Planarity testing given an embedding 3 Number of planar graphs, given an embedding 2 Showing asymptotic lower bound on log of recurrence 2 Existence of good error correcting codes

### Tags (191)

 89 time-complexity × 43 49 big-o-notation × 17 85 complexity-theory × 54 44 dijkstras-algorithm × 3 82 turing-machines × 60 43 arrays × 7 79 algorithms × 72 39 iteration × 2 63 graphs × 32 37 linear-complexity

### Bookmarks (3)

 4 Universal approximation bounds of the form $\|f(x)-\hat{f}(x;w)\|\leq \varepsilon \|f(x)\|$ 2 Expressing functions using the arithmetic dictionary 2 Showing asymptotic lower bound on log of recurrence