What's the deal with Deno? We talk with a major contributor to find out. Listen now.

# Tag Info

43

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

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

20

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

19

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

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

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

13

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

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

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

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

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

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

The problem with your intuition is that, frankly, you don't have one. At least not a useful, that is algorithmic one, one that tells you what is hard for computers and what is not. You think in terms of what you can do with every-day data -- but that's not an appropriate frame of reference for this problem. As evidence, consider this question. Some specific ...

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

L is recognizable A language $L$ is recognizable if and only if there exists a verifier for $L$, where a verifier is a Turing machine that halts on all inputs and for all $w \in \Sigma^*$, $w \in L \leftrightarrow \exists c \in \Sigma^*. V\text{ accepts }\langle w, c\rangle$. Commonly, $c$ is thought of as a "certificate" or "proof" that $w$ is in $L$ and ...

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

6

Your intuition is exactly right. Yes, that's equivalent to choosing a random polynomial over $\mathbb{F}_p$. The reason why it works is exactly the interpolation theorem for finite fields. $k$-wise independent basically means "it behaves like a perfect hash function, if you only feed it $k$ inputs" or "it behaves like a perfect hash function, as far as ...

5

Those are typically algorithms of the "divide and conquer" variety, where the cost of dividing and combining subsolutions isn't "too large". Take a look at this FAQ to see what kinds of recurrences give rise to this behaviour.

5

Another detail that may help your intuition is that an Euler cycle exists if and only if each vertex has even degree. A similar theorem exists for Euler paths. This follows from a fairly straightforward proof--basically, every time you visit a vertex, you must then leave it, so each "visit" takes two from the degree of the vertex. This doesn't explain why ...

5

the Turing proof is quite similar to Cantors proof that the cardinality of reals ("uncountable") is larger than the cardinality of the rationals ("countable") because they cannot be put into 1-1 correspondence but this is not noted/ emphasized in very many references (does anyone know any?). (iirc) a CS prof once showed this years ago in class (not sure ...

5

A language $L$ is NP-hard if for every language $R$ in NP there exists a function $f$ computable in polynomial time such that for all $x$, $x \in R$ iff $f(x) \in L$. A language $L$ is coNP-hard if for every language $R$ in coNP there exists a function $f$ computable in polynomial time such that for all $x$, $x \in R$ iff $f(x) \in L$. If a language is ...

5

If you want to use lookup tables, and you have 4GB of memory, you'll only be able to use a lookup table with about $2^{32}$ entries or fewer, so you'll only be able to handle multiplication of numbers that are at most 16 bits long. If you want to multiply larger numbers, you won't be able to use lookup tables for multiplication. Typically we want to ...

4

Is it the case that time complexity is always an increasing function in the input size? If so, why is it the case? Is there a proof for that beyond hand-waving? Let $n$ denote the input size. To read the entire input, a turing machine already needs $n$ steps. So if you assume that an algorithm has to read it's entire input (or $n/c$ for some constant \$...

4

If you think convolution is a little too hard to understand, I recommend you start searching about Mathematical Morphology applied to image processing, the big idea behind Mathematical Morphology is that you'll do a operation very close to the convolution, to "change" the morphology of the image, but retain the topology information, this way, you can make a ...

4

Although all tautologies can be rewritten into "true", several of them are known since classic times under specific names. After all philosophers had to learn and analyse the type of arguments they were using. With the help of google I managed to find this proposition you refer to. It is known as "Clavius's Law" or "Consequentia mirabilis".

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