# Tag Info

53

The $\Theta(\log n)$ complexity is usually connected with subdivision. When using lists as an example, imagine a list whose elements are sorted. You can search in this list in $\mathcal{O}(\log n)$ time - you do not actually need to look at each element because of the sorted nature of the list. If you look at the element in the middle of the list and ...

41

Let's refresh the definitions. PSPACE is the class of problems that can be solved on a deterministic Turing machine with polynomial space bounds: that is, for each such problem, there is a machine that decides the problem using at most $p(n)$ tape cells when its input has length $n$, for some polynomial $p$. EXP is the class of problems that can ...

38

In terms of (balanced) trees (say, binary tree, so all $\log$'s are base 2): $\Theta(1)$ is getting the root of the tree $\Theta(\log n)$ is a walk from root to leaf $\Theta(n)$ is traversing all nodes of the tree $\Theta(n^2)$ is actions on all the subsets two nodes in the tree, e.g., the number of different paths between any two nodes. $\Theta(n^k)$ - ...

22

Expanding my comment: Dependent types can type more programs. "More" simply means that the set of programs typable with dependent types is a proper superset of the programs typable in the simply-typed $\lambda$-calculus (STLC). An example would be $List_{2*3+4}(\alpha)$, the lists of length $10$, carrying elements of type $\alpha$. The expression $2*3+4$ is ...

18

It may be simply that it's mistaken to think that someone would reason their way to this argument without making a similar argument at some point prior, in a "simpler" context. Remember that Turing knew Cantor's diagonalisation proof of the uncountability of the reals. Moreover his work is part of a history of mathematics which includes Russell's paradox (...

18

In your edit, you write: What I still don't see is what would motivate someone to define $D(M)$ based on $M$'s "self-application" $M;M$, and then again apply $D$ to itself. That seems to be less related to diagonalization (in the sense that Cantor's argument did not have something like it), although it obviously works well with diagonalization once you ...

17

For $O(\log n)$ to be possible, you need to be able to cut down the problem size proportionally by some arbitrary amount with respect to $n$ with a constant time operation. For example, in the case of binary search, you can cut down the problem size by a half with each comparison operation. Now, do you have to cut down the problem size by half, actually no....

17

Your archetypical $\Theta(n \log n)$ is a divide-and-conquer algorithm, which divides (and recombines) the work in linear time and recurses over the pieces. Merge sort works that way: spend $O(n)$ time splitting the input into two roughly equal pieces, recursively sort each piece, and spend $\Theta(n)$ time combining the two sorted halves. Intuitively, ...

15

Abstraction is pretty much bread and butter in computer science but unfortunately it is hard to teach explicitly. In my opinion, understanding concepts is more important than being able to mechanically calculate or prove stuff. Sure, you need to know your way around some elementary methods, but the meat lies elsewhere. First of all, you have to grasp the ...

15

This is my personal approach to determine whether a problem (i.e. a language $L$) is NP-complete or not. If both these conditions are verified: I feel that testing if an instance $I$ is in $L$ implies that I need to check all combinations of some sort and that there is no way to split such a combination into two smaller ones then $L$ may very well be NP-...

14

Another perspective on problem-hardness comes from the game and puzzle community, where the rule of thumb is that 'problems are as hard as they possibly can be' (and the exceptions come from hidden structures in the problem - Massimo's example of the determinant in comments is a good instance of this); the trick then comes in understanding how hard a problem ...

13

I think the simplest way to think of Convolution is as a method of changing a pixel's value to a new value based on the weight of nearby pixels. It's easy to see why Box Blur: _____________ |1/9|1/9|1/9| |1/9|1/9|1/9| |1/9|1/9|1/9| ------------- works. Convolving this kernel is the same as going through every pixel of a photo and making the new value of ...

12

Is it the case that time complexity is always an increasing function in the input size? If so, why is it the case? No. Consider a Turing machine that halts after $n$ steps when the input size $n$ is even, and halts after $n^2$ steps when $n$ is odd. If you mean the complexity of a problem, the answer is still no. The complexity of primality testing is ...

12

Maybe the following perspective helps: When you are trying to construct a Eulerian path, you can proceed almost greedily. You just start the path somewhere and the try to walk as long as possible. If you detect a circle, you will delete its edges (but record that this circle was constructed). By this you decompose the graph in circles, which can be easily ...

11

The main property of DFA's/NFA's is the lack of unbounded memory. If you look at a language and the only algorithm (which should later be translated into a Finite Automaton) you can think of requires this property, that is, you feel that any algorithm that recognizes it will need to remember an arbitrary large number of things (like $n$ in your example) then ...

11

Two other categories of algorithms that take $\Theta(n \log n)$ time: Algorithms where each item is processed in turn, and it takes logarithmic time to process each item (e.g. HeapSort or many of the plane sweep computational geometry algorithms). Algorithms where the running time is dominated by a sorting pre-processing step. (For example, in Kruskal's ...

11

This is exactly the incorrect interpretation of "computable", resulting of trying to replace the precise definition with (possibly misplaced) intuition. $\pi$ or any other irrational number also has an infinite digit representation, so according to your logic, it shouldn't be computable. This just shows that it is meaningless to require all of the digits as ...

9

What's missing is the way you run the Turing Machine $M$ on strings to get the Enumerator. Rather than generate each string, run $M$, and then output this string if the $M$ accepts – which as you identified will not work – you do something like the following, which adopts the strategy of simulating many instances of the $M$ on different strings "in parallel"...

9

Another category: Algorithms in which the output has size $\Theta(n \log n)$, and therefore $\Theta(n \log n)$ running time is linear in the output size. Although the details of such algorithms often use divide-and-conquer techniques, they don't necessarily have to. The run-time fundamentally comes from the question being asked, and so I think it is worth ...

9

A machine running in exponential time could use exponential space. So a priori it could be that machines restricted to polynomial space would be weaker. A similar situation occurs for P and L. A machine running in polynomial time could use polynomial space, so a priori it could be that machines restricted to logarithmic space would be weaker. It is even ...

9

Self application is not a necessary ingredient of the proof In a nutshell If there is a Turing machine $H$ that solves the halting problem, then from that machine we can build another Turing machine $L$ with a halting behavior (halting characteristic function) that cannot be the halting behavior of any Turing machine. The paradox built on the self applied ...

8

Think about algorithm to convert decimal number $n$ to binary while n != 0: print n%2, n = n/2 This while loop runs $\log(n)$ times.

8

Yes, $\log(n)$ is between $1$ and $n$, but it is closer to $1$ than $n$. What is $\log(n)$? The log function is the inverse function of exponentation. Let me start with exponentation and you should get a better idea of what logarithm is. Consider two numbers, $100$ and $2^{100}$. $2^{100}$ is $2$ multiplied with itself $100$ times. You can with some effort ...

8

I sometimes find out that people that don't do well in theory, just have the basics wrong (on the first 1-3 lectures, they thought the material is very easy, so they didn't pay too much attention, but then, at lecture 5-7 things speed up and it's too late to recap). As @fbernardo said, it might be a good idea to start from the beginning. NOT as far as FLA (...

8

Proving the correctness of a program in a form of a proof that's nothing but the program itself This is not quite how the Curry-Howard-Correspondence works. First one has to show that the language of choice actually corresponds to some consistent logic. Different languages correspond to different logics, and many languages correspond to inconsistent ...

8

There is also a proof of this fact that uses a different paradox, Berry's paradox, which I heard from Ran Raz. Suppose that the halting problem were computable. Let $B(n)$ be the smallest natural number that cannot be computed by a C program of length $n$. That is, if $S(n)$ is the set of natural numbers computed by C programs of length $n$, then $B(n)$ is ...

7

A complete understanding of what J was actually saying and why has only come fairly recently. This blog post discusses it. While thinking in terms of homotopy and continuous functions provides a lot of intuition and connects to a very rich area of mathematics, I'm going to try to keep the discussion below at the logical level. Let's say you axiomatized ...

6

To expand on Artem's comment, note that if we have an $m$ state automaton, at each point we can remember at most $\lg m$ bits of information about the part of input we have read so far. Based on this finite amount of information about the the previous bits of the input, you should be able to end up in the right accepting/rejecting state for all possible ways ...

6

One way to think about convolution/crosscorrelation is as if you were searching for some signal in your data. The more the data looks like the kernel, the higher the resulting value will be. I actually take the reverse of the kernel, i.e. as in cross-correlation, but it is basically the same thing. For example, let's say you are looking for a directional ...

6

A complexity of $O(n\log n)$ arises from divide and conquer algorithms which divide their input into $k$ pieces of roughly equal size in time $O(n)$, operate on these pieces recursively, and then combine them in time $O(n)$. If you only operate on some of the pieces, the running time drops to $O(n)$.

Only top voted, non community-wiki answers of a minimum length are eligible