Questions tagged [terminology]

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

Filter by
Sorted by
Tagged with
37 votes
2 answers

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 ...
Marc Hamann's user avatar
  • 2,904
15 votes
2 answers

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 ...
Federico Magallanez's user avatar
39 votes
6 answers

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 ...
Greg Bacon's user avatar
14 votes
1 answer

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)$ ...
David G's user avatar
  • 532
10 votes
2 answers

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,...
Aaron Roth's user avatar
  • 9,850
54 votes
11 answers

If you could rename dynamic programming...

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

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?
z5h's user avatar
  • 323
17 votes
2 answers

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 ...
Vijay D's user avatar
  • 12.6k
17 votes
1 answer

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 ...
Arindam Pal's user avatar
  • 1,591
8 votes
2 answers

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 ...
Luca Trevisan's user avatar
6 votes
1 answer

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 ...
IV1's user avatar
  • 63
5 votes
1 answer

$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 ...
David Harris's user avatar
  • 3,488
4 votes
2 answers

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 ...
Rhymoid's user avatar
  • 167
3 votes
0 answers

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 ...
Vag's user avatar
  • 443
2 votes
1 answer

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 ...
user3266's user avatar