Questions tagged [terminology]
questions about definitions, terms, and common names in theoretical computer science.
15
questions
37
votes
2
answers
6k
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 ...
- 2,904
15
votes
2
answers
6k
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
6
answers
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 ...
- 629
14
votes
1
answer
988
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)$ ...
- 532
10
votes
2
answers
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,...
- 9,850
54
votes
11
answers
5k
views
If you could rename dynamic programming...
If you could rename dynamic programming, what would you call it?
22
votes
4
answers
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?
- 323
17
votes
2
answers
4k
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 ...
- 12.6k
17
votes
1
answer
701
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 ...
- 1,591
8
votes
2
answers
553
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 ...
- 4,902
6
votes
1
answer
280
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 ...
- 63
5
votes
1
answer
937
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 ...
- 3,488
4
votes
2
answers
245
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 ...
- 167
3
votes
0
answers
377
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 ...
- 443
2
votes
1
answer
245
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 ...
- 37