# Questions tagged [terminology]

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

163 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 ...
31k 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 ...
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 ...
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))$. ...
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 ...
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". ...
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 ...
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. ...
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" (...
876 views

### Sums of Landau terms revisited

I asked a (seed) question about sums of Landau terms before, trying to gauge the dangers of abusing asymptotics notation in arithmetics, with mixed success. Now, over here our recurrence guru JeffE ...
33k views

### In a DFA, does every state have a transition on every symbol of the alphabet?

If not, then what does it mean when for some state $q$ and some symbol $a$, $\delta(q, a)$ does not exist?
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 ...
10k 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 ...
17k views

### algorithm time analysis "input size" vs "input elements"

I'm still a bit confused with the terms "input length" and "input size" when used to analyze and describe the asymptomatic upper bound for an algorithm Seems that input length for the algorithm ...
16k 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. ...
1k views

### Classfication of randomized algorithms

From Wikipedia about randomized algorithms One has to distinguish between algorithms that use the random input to reduce the expected running time or memory usage, but always terminate with a ...
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 ...
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 ...
45k 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 ...
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 ...
11k views

### PTAS definition vs. FPTAS

From what I read in the ...
12k views

### Word- or byte-addressable? Correct terminology

Seemingly, a byte has established itself to be 8bit (is that correct?). RAM and NOR-flash can be normally accessed on a quite granular level, but it is up to the system architecture to determine if ...
19k views

### What is difference between architecture and microarchitecture?

I am studying computer architecture. I would like to know the difference between the terms "computer architecture" and "microarchitecture".
5k views

### What's a trivial property?

I have to show a property P is trivial. This problem has to do with Rice's Theorem, which I do not completely understand. Can someone explain the difference between trivial and non-trivial properties?...
3k views

### Importance of the empty string

In the sense of a string distinct from a null reference string, what is the importance of an empty string in CS (and specially in formal languages)? Why do you need a separate concept, that of '...
1k views

### What constitutes one unit of time in runtime analysis?

When calculating runtime dependence on the input, what calculations are considered? For instance, I think I learned that array indexing as well as assignment statements don't get counted, why is that?
6k views

### What do f(x) and g(x) represent in Big O notation?

I have been reading about Big O notation. People writing about Big O often use the terms $f(x)$ and $g(x)$. For instance, I often see people write things like $f(x) = O(g(x))$ or $f(x) \in O(g(x))$. ...
204 views

### What are the justifications and historical reasons regarding the choice between the words 'calculus' and 'algebra'?

The principles of calculus, historically, are differentials and integrals , while those of algebra are operators and equation solving . Contemporary principles are analysis and abstract objects, ...
1k views

### Definition of $\Theta$ for negative functions

I'm working out of the 3rd edition CLRS Algorithms textbook and in Chapter 3 a discussion begins about asymptotic notation which starts with $\Theta$ notation. I understood the beginning definition of:...
12k views

### Call by value-result vs. call by reference?

From my Googling, it appears that call by value-result is similar to call by reference in that it changes values in the caller, but it's different in that the changes don't take place until the callee ...
2k views

### When generating a PDA from a CFG do I have a receiving state?

Thw Wikipedia article on Pushdown automata doesn't explain what the receiving state is for the generated PDA it just states that there is but one state.
2k views

2k views

### Is there a theory/abstraction behind OOP?

Functional programming has the very elegant Lambda Calculus and its variants as a backup theory. Is there such a thing for OOP? What is an abstraction for the object oriented model?
2k views

### Importance of recursion in computability theory

It is said that computability theory is also called recursion theory. Why is it called like that? Why recursion has this much importance?
6k views

### Good way to describe co-RE (co-recursively enumerable)?

I get that R is a set of languages that are decidable by a Turing Machines And that RE is a set of languages that a each language can be recognized by a TM, that is the machine will halt when given a ...
10k views

### What is an Efficient Algorithm?

From the point of view of asymptotic behavior, what is considered an "efficient" algorithm? What is the standard / reason for drawing the line at that point? Personally, I would think that anything ...
4k views

### What is a "reduction", really?

I am studying computational theory with Sipser's textbook. I can't quite understand the definition of "reduction". For example, "this problem can be reduced to ATM ..." What exactly does "to reduce" ...
439 views

### Is there a canonical definition of “pure” function?

StackOverflow pointed me here, so the question might be a bit in a layman's terms. Wikipedia defines pure functions as In computer programming, a function may be described as a pure function if ...
8k views

### NFAs with more than one initial state

I'm trying to give a meaningful definition for NFAs with more than one initial state. I know from the formal definition in Wikipedia that it is possible to have more than one initial state, it ...
5k views

### What is a partially computable function?

In the book Computability, Complexity, and Languages, Martin Davis writes in chapter two: A partial function is said to be partially computable if it is computed by some program. and also A ...
2k views

### What is the difference between the semantic and syntactic views of function types?

Edit: My original question referred to nonconstructive and constructive definitions of function types. I changed the terminology in the question and the title to semantic and syntactic, which the ...