# Questions tagged [terminology]

Questions about how specific notions have to be understood as well as conventions of notation.

1,076 questions
Filter by
Sorted by
Tagged with
142k views

### What is the definition of P, NP, NP-complete and NP-hard?

I'm in a course about computing and complexity, and am unable to understand what these terms mean. All I know is that NP is a subset of NP-complete, which is a subset of NP-hard, but I have no idea ...
30k views

### How does one know which notation of time complexity analysis to use?

In most introductory algorithm classes, notations like $O$ (Big O) and $\Theta$ are introduced, and a student would typically learn to use one of these to find the time complexity. However, there are ...
25k views

### Why is the unit of image size not Pixel²?

If you calculate the area of a rectangle, you just multiply the height and the width and get back the unit squared. Example: 5cm * 10cm = 50cm² In contrast, if you calculate the size of an image, you ...
8k views

### What does the "Lambda" in "Lambda calculus" stand for?

I've been reading about Lambda calculus recently but strangely I can't find an explanation for why it is called "Lambda" or where the expression comes from. Can anyone explain the origins of the term?...
9k views

### What is coinduction?

I've heard of (structural) induction. It allows you to build up finite structures from smaller ones and gives you proof principles for reasoning about such structures. The idea is clear enough. But ...
13k views

### Dependent types vs refinement types

Could somebody explain the difference between dependent types and refinement types? As I understand it, a refinement type contains all values of a type fulfilling a predicate. Is there a feature of ...
70k views

### Distributed vs parallel computing

I often hear people talking about parallel computing and distributed computing, but I'm under the impression that there is no clear boundary between the 2, and people tend to confuse that pretty ...
7k views

### Why polynomial time is called "efficient"?

Why in computer science any complexity which is at most polynomial is considered efficient? For any practical application(a), algorithms with complexity $n^{\log n}$ are way faster than algorithms ...
4k views

### What is the meaning of $O(m+n)$?

This is a basic question, but I'm thinking that $O(m+n)$ is the same as $O(\max(m,n))$, since the larger term should dominate as we go to infinity? Also, that would be different from $O(\min(m,n))$. ...
8k views

### What is the difference between an algorithm, a language and a problem?

It seems that on this site, people will often correct others for confusing "algorithms" and "problems." What are the difference between these? How do I know when I should be considering algorithms and ...
49k views

### Difference between Parallel and Concurrent programming?

When looking at concurrent programming, two terms are commonly used i.e. concurrent and parallel. And some programming languages specifically claim support for parallel programming, such as Java. ...
8k views

### Perplexed by Rice's theorem

Summary: According to Rice's theorem, everything is impossible. And yet, I do this supposedly impossible stuff all the time! Of course, Rice's theorem doesn't simply say "everything is impossible". ...
48k views

### What exactly (and precisely) is "hash?"

I have heard the word "hash" being used in different contexts (all within the world of computing) with different meanings. For example, in the book Learn Python the Hard Way, in the chapter on ...
4k views

### What is the definition of Computer Science, and what is the Science within Computer Science?

I am pursuing a BS in Computer Science, but I am at an early point of it, and I am pretty sure I will be happy with my choice given that it seems like an academically and career flexible education to ...
75k views

### What exactly is polynomial time? [duplicate]

I'm trying to understand algorithm complexity, and a lot of algorithms are classified as polynomial. I couldn't find an exact definition anywhere. I assume it is the complexity that is not exponential....
8k views

### What is the name the class of functions described by O(n log n)?

In "Big O", common notations have common names (instead of saying, "Oh of some constant factor"): O(1) is "Constant" O(log n) is "Logarithmic" O(n) is "Linear" O(n^2) is "Quadratic" O(n * log n) ...
4k views

### What does "context" in "context-free grammar" refer to?

There are lots of definitions online about what a Context-Free Grammar is, but nothing I find is satisfying my primary trouble: What context is it free of? To investigate, I Googled "context ...
46k views

### Difference between a turing machine and a finite state machine?

I am doing a presentation about Turing machines and I wanted to give some background on FSM's before introducing Turing Machines. Problem is, I really don't know what is VERY different from one ...
12k views

### Differences and relationships between randomized and nondeterministic algorithms?

What differences and relationships are between randomized algorithms and nondeterministic algorithms? From Wikipedia A randomized algorithm is an algorithm which employs a degree of randomness ...
44k views

After reading several sources I'm still confused about user- and kernel-level threads. In particular: Threads can exist at both the user level and the kernel level What is the difference between ...
3k views

### Why is a regular language called 'regular'?

I have just completed the first chapter of the Introduction to the Theory of Computation by Michael Sipser which explains the basics of finite automata. He defines a regular language as anything ...
5k views

### Explaining the difference between computer science and computer literacy [closed]

What is a good metaphor or example to explain to an English major the difference between classical computer science and "being good with using MS-Windows" computer science computer programming ...
4k views

### What does 'true concurrency' mean?

I often hear phrases like 'true concurrency semantics' and 'true concurrency equivalences' without any references. What does those terms mean and why are they important? What are some examples of ...
3k views

### What's really meant by context-free in the term context-free grammar?

I have been studying compilers for a while, and I have been searching what's meant by "context" in grammar and what it means for grammar to be "context-free", but with no result. So can anyone help ...
16k views

### Is O(mn) considered "linear" or "quadratic" growth?

If I have some function whose time complexity is O(mn), where m and n are the sizes of its two inputs, would we call its time complexity "linear" (since it's linear in both m and n) or "quadratic" (...
39k views

### What is the difference between object detection, semantic segmentation and localization?

I've read those words in quite a lot of publications and I would like to have some nice definitions for those terms which make it clear what the difference between object detection vs semantic ...
10k views

### "NP-complete" optimization problems

I am slightly confused by some terminology I have encountered regarding the complexity of optimization problems. In an algorithms class, I had the large parsimony problem described as NP-complete. ...
9k views

### Is there a name for the class of algorithms that are the most efficient for a particular task?

This would be analogous to the Kolmogorov complexity of a string, except that in this case, I'm interested in the algorithm that solves a given problem using the least number of steps. We would ...
12k views

### Why is A implies B true if A is false and B is false?

It seems to me that the 'implies' in English language does not mean the same thing as the logical operator 'implies', in a similar way how 'OR' word in most cases means 'Exclusive OR' in our everyday ...
4k views

### Why are computable functions also called recursive functions?

In computability theory, computable functions are also called recursive functions. At least at first sight, they do not have anything in common with what you call "recursive" in day-to-day programming ...
4k views

### What are staged functions (conceptually)?

In a recent CACM article , the authors present an implementation for staged functions. They use the term as if it was well-known, and none of the references looks like an obvious introduction. ...
5k views

### Distinguish Decision Procedure vs SMT solver vs Theorem prover vs Constraint solver

Those terminologies confuse me. As I understand SAT solver: decide the satisfiability of propositional logic (using DPLL or Local Search). Decision procedure is a procedure to decide the ...
15k views

### What is meant by "solvable by non deterministic algorithm in polynomial time" [duplicate]

In many textbooks NP problems are defined as: Set of all decision problems solvable by non deterministic algorithms in polynomial time I couldn't understand the part "solvable by non deterministic ...
12k views

### What is the significance of reverse polish notation?

I teach computing to 18 year olds. After having reverse polish notation (RPN) explained to them, one asked why is it significant enough to be in the public exam. I explained the historical ...
3k views

### What is beta equivalence?

In the script I am currently reading on the lambda calculus, beta equivalence is defined as this: The $\beta$-equivalence $\equiv_\beta$ is the smallest equivalence that contains $\rightarrow_\beta$...
3k views

### What exactly is computation?

I know what computation is in some vague sense (it is the thing computers do), but I would like a more rigorous definition. Dictionary.com's definitions of ...
48k views

### What are the differences between computer vision and image processing?

What are the differences between computer vision and image processing? For example, in object recognition, what are the roles of computer vision and image processing?
3k views

### How to read typing rules?

I started reading more and more language research papers. I find it very interesting and a good way to learn more about programming in general. However, there usually comes a section where I always ...
6k views

### Fixed point, what does it mean in the world of computer science

I keep coming across references to fixed point in questions and answers at stackexchange and I look up the meaning on the web obviously finding reference at sites such as Wikipedia. However none of ...
3k views

### How can I academically say that 'one computer is slower than the other'?

I'm writing a research paper and I have to basically say that one microcontroller is slower than an other microprocessor. However, I'm worried that simply saying that it's 'slower' wouldn't be ...
15k views

### How is Dynamic programming different from Brute force

I was reading up on Dynamic Programming when I came across the following quote A dynamic programming algorithm will examine all possible ways to solve the problem and will pick the best solution. ...
32k views

### What is the difference between finite automata and finite state machines?

I have used FSM in Digital sequential Circuit designs. But I am unfamiliar with Finite Automata. Can somebody help me in understanding 'basic' difference between the two ?
3k views

### Who coined the term "machine learning"?

I'm trying to figure out who coined the term "machine learning". An ancillary question is from where is Arthur Samuel cited as defining the field of "machine learning" in 1959 as: the field of ...
551 views

### Is there a theory of exception hierarchies?

I'm familiar with a dozen of programming languages which have exceptions in some way, yet I came to witness two "pathological" tendencies. There doesn't seem to be a common pattern or ...
7k views

### Difference between time complexity and computational complexity

For measuring the complexity of an algorithm, is it time complexity, or computational complexity? What is the difference between them? I used to calculate the maximum (worst) count of basic (most ...
42k views

### Infinite Language vs. finite language

I'm unclear about the use of the phrases "infinite" language or "finite" language in computer theory. I think the root of the trouble is that a language like $L=\{ab\}^*$ is infinite in the sense ...
17k views

### What is the purpose of using NIL for representing null nodes?

In my Algorithms and Data Structures course, professors, slides and the book (Introduction to Algorithms, 3rd edition) have been using the word NIL to denote for ...
2k views

### What guarantees do "soft" real-time operating systems actually provide

I think I know what a "hard" real-time operating system is. It is an operating system with a scheduler that provides a contract with the application programmer. An application provides a deadline ...