The tag has no wiki summary.

learn more… | top users | synonyms

6
votes
1answer
270 views

Describing state machines mathematically

The short paper "Computer Science and State Machines" by Leslie Lamport seems quite strange to me. On the one hand, I am surprised to see that an important hardware protocol called "two-phase ...
2
votes
0answers
381 views

What's the hardest problem with a non-trivial exact algorithm?

Exact algorithms for NP-complete problems are sometimes feasible, if the input is small enough. I’ve also came across some algorithms which are not practical even for very small inputs, and their ...
5
votes
0answers
160 views

Examples of simple charging schemes

I am looking for a simple example of a charging scheme. That is, one that will take 1-2 minutes to explain in a talk. I know of one such example, though it concerns a geometric question, while I hope ...
2
votes
2answers
1k views

Recursively enumerable, non-recursive language without using Gödel's number

I am trying to find out if there exists a language, which is recursively enumerable but not recursive, but which wouldn't also use Gödel's number or any other kind of Turing machine description in its ...
2
votes
1answer
738 views

Maximum clique algorithm on undirected graph

Recently I learned about maximum cliques. For fun I came up with an algorithm (described below) to find the maximum cliques in an undirected graph. I'd just like some help constructing a graph s.t. ...
49
votes
11answers
5k views

Common false beliefs in theoretical computer science

EDIT AT 10/12/08: I'll try to modified the question so it may interest more people to share their opinions. We NEED your contributions! This post is inspired by the one in MO: Examples of common ...
8
votes
5answers
554 views

Examples in which the size of the alphabet ($\geq 2$) used for an encoding matters

Let $\Sigma$ be an alphabet, ie a nonempty finite set. A string is any finite sequence of elements (characters) from $\Sigma$. As an example, $ \{0, 1\}$ is the binary alphabet and $0110$ is a string ...
45
votes
14answers
1k views

Where and how did computers help prove a theorem?

The purposes of this question is to collect examples from theoretical computer science where the systematic use of computers was helpful in building a conjecture that lead to a theorem, falsifying a ...