366

I think the Wikipedia articles $\mathsf{P}$, $\mathsf{NP}$, and $\mathsf{P}$ vs. $\mathsf{NP}$ are quite good. Still here is what I would say: Part I, Part II [I will use remarks inside brackets to discuss some technical details which you can skip if you want.] Part I Decision Problems There are various kinds of computational problems. However in an ...


228

Because "pixel" isn't a unit of measurement: it's an object. So, just like a wall that's 30 bricks wide by 10 bricks tall contains 300 bricks (not bricks-squared), an image that's 30 pixels wide by 10 pixels tall contains 300 pixels (not pixels-squared).


180

Part II Continued from Part I. The previous one exceeded the maximum number of letters allowed in an answer (30000) so I am breaking it in two. $\mathsf{NP}$-completeness: Universal $\mathsf{NP}$ Problems OK, so far we have discussed the class of efficiently solvable problems ($\mathsf{P}$) and the class of efficiently verifiable problems ($\mathsf{...


124

I have a different answer from other folks: pixel is the correct unit for areas, and you do need dimensional analysis. The discrepancy is that the pixel in "3840 pixels wide" is not the same unit as the pixel in "the display has 8294400 pixels". Instead, "pixel" is a natural-language abbreviation for different units at different times, and it takes some ...


82

An excerpt from History of Lambda-calculus and Combinatory Logic by F. Cardone and J.R. Hindley(2006): By the way, why did Church choose the notation “$\lambda$”? In [Church, 1964, §2] he stated clearly that it came from the notation “$\hat{x}$” used for class-abstraction by Whitehead and Russell, by first modifying “$\hat{x}$” to “$\wedge x$” to ...


76

You are referring to the Landau notation. They are not different symbols for the same thing but have entirely different meanings. Which one is "preferable" depends entirely on the desired statement. $f \in \cal{O}(g)$ means that $f$ grows at most as fast as $g$, asymptotically and up to a constant factor; think of it as a $\leq$. $f \in o(g)$ is the ...


60

First, to dispel a possible cognitive dissonance: reasoning about infinite structures is not a problem, we do it all the time. As long as the structure is finitely describable, that's not a problem. Here are a few common types of infinite structures: languages (sets of strings over some alphabet, which may be finite); tree languages (sets of trees over some ...


57

This is partly a matter of terminology, and as such, only requires that you and the person you're talking to clarify it beforehand. However, there are different topics that are more strongly associated with parallelism, concurrency, or distributed systems. Parallelism is generally concerned with accomplishing a particular computation as fast as possible, ...


53

For simplicity, I'll begin by only considering "decision" problems, which have a yes/no answer. Function problems work roughly the same way, except instead of yes/no, there is a specific output word associated with each input word. Language: a language is simply a set of strings. If you have an alphabet, such as $\Sigma$, then $\Sigma^*$ is the set of all ...


52

It's called linearithmic time, and is a special case of a more general class known as quasi linear. As the name may suggests, the algorithms that fall in this class almost run in linear time; in fact they have a lower complexity than algorithms which run in $O(n^k)$ with $k > 1$.


44

The Wikipedia article on hash functions is very good, but I will here give my take. What is a hash? "Hash" is really a broad term with different formal meanings in different contexts. There is not a single perfect answer to your question. I will explain the general underlying concept and mention some of the most common usages of the term. A "hash" is ...


44

A pixel is already a two-dimensional object In your example, you specify centimeters as a contrasting example. Centimeters are a unit of length, which is by nature a one-dimensional measurement. When measuring areas, we need to talk about square centimeters, which defines the unit as a two-dimensional quadrilateral with right angles and equal length sides = ...


43

Big O: upper bound “Big O” ($O$) is by far the most common one. When you analyse the complexity of an algorithm, most of the time, what matters is to have some upper bound on how fast the run time¹ grows when the size of the input grows. Basically we want to know that running the algorithm isn't going to take “too long”. We can't express this in actual time ...


40

Polynomial time algorithms are algorithms whose running time increases by a constant factor when the input is doubled in size. Exponential time algorithms are algorithms whose running time increases by a constant factor when the input size increases by 1. For laypeople you can perhaps identify NP-complete problems with problems solvable only in exponential ...


38

Computer science is a misnomer - there is actually no "science" in computer science, since computer science is not about observing nature. Rather, parts of computer science are engineering, and parts are mathematics. The more theoretical parts of computer science are purely mathematical. For example, what is a good algorithm for sorting? How do we define ...


38

Let me see if I can clear up a few potential misconceptions here. Sometimes people think that when they write a research paper they have to use fancy language: it's not enough to just say what they mean, but rather, it has to be written in academic code with more complex-sounding language. Or, they think that using bigger words will make them sound more ...


38

Humans are bad at logic until they have to employ it to figure out human affairs. Think of "if $A$ then $B$" as a kind of promise: "I promise to you that if you do $A$ then I will do $B$". Such a promise says nothing about what I might do if you fail to do $A$. In fact, I might do $B$ anyhow, and that would not make me a liar. For instance, suppose your ...


38

Would it be incorrect to cast polynomial time as "time measured in (computational) operations?" Yes. Completely incorrect. "Time" does indeed mean "time measured in (computational) operations" but you've not translated "polynomial" at all. It's like translating "twelve days" as "time measured in number of rotations of the earth on its axis." That's exactly ...


37

You are right, there always is a context in some sense. I don't think you can understand what "context" means in "context-free" without understanding a production. A production is a substitution rule. It says that, to generate strings within the language, you can substitute what is on the left for what is on the right: A -> xy This means that the ...


36

Fundamental misunderstanding: Every property of a computer program is non-computable That is not what Rice's theorem talks about. It talks about properties of functions and that the set of programs computing this function is not decidable. Formally, given $\emptyset \subset P \subset \mathsf{RE}$ the set $\qquad \displaystyle \{ \langle M \rangle \mid ...


36

For the purposes of this discussion, a "program" is a piece of code which always takes an integer as an input, and either runs forever or returns an integer. We say that two programs $f$ and $g$ are extensionally equal if they compute the same function, i.e., for every number $n$ either both $f(n)$ and $g(n)$ run forever, or they both terminate and output ...


34

An algorithm is polynomial (has polynomial running time) if for some $k,C>0$, its running time on inputs of size $n$ is at most $Cn^k$. Equivalently, an algorithm is polynomial if for some $k>0$, its running time on inputs of size $n$ is $O(n^k)$. This includes linear, quadratic, cubic and more. On the other hand, algorithms with exponential running ...


33

You are right. Notice that the term $O(n+m)$ slightly abuses the classical big-O Notation, which is defined for functions in one variable. However there is a natural extension for multiple variables. Simply speaking, since $$ \frac{1}{2}(m+n) \le \max\{m,n\} \le m+n \le 2 \max\{m,n\},$$ you can deduce that $O(n+m)$ and $O(\max\{m,n\})$ are equivalent ...


33

The main differences are along two dimensions -- in the underlying theory, and in how they can be used. Lets just focus on the latter. As a user, the "logic" of specifications in LiquidHaskell and refinement type systems generally, is restricted to decidable fragments so that verification (and inference) is completely automatic, meaning one does not require ...


32

Another perspective on "efficiency" is that polynomial time allows us to define a notion of "efficiency" that doesn't depend on machine models. Specifically, there's a variant of the Church-Turing thesis called the "effective Church-Turing Thesis" that says that any problem that runs in polynomial time on on kind of machine model will also run in polynomial ...


30

The context can be explained with regards to the production rules allowed for different grammars in Chomsky hierarchy. If you consider context-free grammars, their production rules have the following form: $$ A \rightarrow \alpha$$ So, you can observe that the left part of this kind of rules is made up of only one non-terminal symbol; thus, the ...


30

What you described is Voronoi diagram. Here is an excerpt from Wikipedia. In the simplest case, shown in the first picture, we are given a finite set of points ${p_1, \cdots, p_n}$ in the Euclidean plane. In this case each site $p_k$ is simply a point, and its corresponding Voronoi cell $R_k$ consists of every point in the Euclidean plane whose ...


29

How about an automotive analogy? uses computers and maybe "is good with computers" :: a driver (can drive and refuel safely) and maybe a car enthusiast (can jump start a car; is familiar with many makes and models; knows techniques like using windshield treatment to keep rain from reducing visibility). programmer :: an automotive mechanic or technician. ...


29

In the most general sense, a key is a piece of information required to retrieve some data. However, this meaning plays out differently depending on exactly what situation you're dealing with. In the contexts you mention, a key is a unique identifier for the complete data used to retrieve it from some location in the structure. Each key is associated with ...


28

One of the roles of a multitasking operating system kernel is scheduling: determining which thread of execution to execute when. So such a kernel has some notion of thread or process. A thread is a sequential piece of code that is executing, and has its own stack and sometimes other data. In an operating system context, people usually use process to mean a ...


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