Questions tagged [terminology]

questions about definitions, terms, and common names in theoretical computer science.

Filter by
Sorted by
Tagged with
31
votes
2answers
4k views

Origins and applications of Theory A vs Theory B?

In a couple recent questions (q1 q2), there has been discussion of "Theory A" vs "Theory B", seemingly to capture the divide between the study of logic and programming languages and the study of ...
15
votes
2answers
4k views

What does 'gadget' mean in NP-hard reduction?

This question may not be technical. As a non-native speaker and a TA for algorithm class, I always wondered what gadget means in 'clause gadget' or 'variable gadget'. The dictionary says a gadget is a ...
39
votes
6answers
6k views

Regular expressions aren't

Ask even someone with a background in computer science what a regular expression is, and the answer is likely to go beyond the constraint of being within reach of a finite-state automaton. For ...
13
votes
1answer
883 views

Equivalent definitions of time constructibility

We say that a function $f:\mathbb{N}\rightarrow\mathbb{N}$ is time-constructible, if there exists a deterministic multi-tape Turing machine $M$ that on all inputs of length $n$ makes at most $f(n)$ ...
49
votes
11answers
4k views

If you could rename dynamic programming…

If you could rename dynamic programming, what would you call it?
22
votes
4answers
1k views

Are there problems without efficient algorithms, where existence theorems have proved such algorithms must exist?

Are there problems in CS where no efficient algorithms are known, despite existence theorems proving such efficient algorithms must exist? What are these problems called? Where can I find out more?
15
votes
2answers
3k views

Is propositional resolution a complete proof system?

This question is about propositional logic and all occurrences of "resolution" should be read as "propositional resolution". This question is something extremely basic but it has been bothering me ...
3
votes
0answers
348 views

Are grammars programs? [closed]

Are grammars programs? That is, are languages for grammar specification programming languages? Update. Motivation for the question is follows: To know whether languages for grammars are programming ...
16
votes
1answer
646 views

Why are perfect graphs called perfect?

Sorry, if this is a naive question, but I could not find the justification in any of the major text books like Bondy-Murty, Diestel or West. Perfect graphs have many beautiful properties, but what is ...
6
votes
2answers
487 views

Terminology for sparse cuts in graphs

I have found some ambiguity in how the graph parameters edge-expansion, uniform sparsest cut and conductance are defined and denoted. My questions are: what are the definitions that best match the ...
9
votes
2answers
2k views

Maximizing sum edge weights

I am wondering if the following problem has a name, or any results related to it. Let $G = (V,w)$ be a weighted graph where $w(u,v)$ denotes the weight of the edge between $u$ and $v$, and for all $u,...
6
votes
1answer
206 views

Equivalent embeddings of a graph

I have difficulties finding a good definition of two embeddings of a (planar) graph in the plane being equivalent. Intuitively I mean by equivalent that the embeddings look the same up to ...
2
votes
1answer
233 views

Searching for name of equivalence property in hamiltonian paths

This one has been bugging me for a while. A long time ago in undergrad, I noticed this while learning about TSP. Nobody recognized it and I basically gave up. Given a hamiltonian path, any subpath ...
5
votes
1answer
651 views

$O(m+n)$ really necessary for graph algorithms?

It is standard to express the running time of linear-time graph algorithms as $O(m+n)$ (such as depth-first-search, etc.). For nearly all such algorithms, vertices of degree zero have no effect on ...
4
votes
2answers
191 views

Can complexities differ w.r.t. different computational models?

I understand that a decision problem can be decidable with respect to certain computational models. For instance, the question whether an arbitrary sequence of parenthesis is balanced is undecidable ...