# Tagged Questions

The tag has no usage guidance.

99 views

### Fractional but not integer multi-commodity minimum cost flow

I'm searching for an example digraph for the multi-commodity minimum cost flow problem with integer demand. There shouldn't be an integer but fractional optimal solution. I found here a similar ...
231 views

### Easy to optimize but hard to evaluate

Are there any known natural examples of optimization problems for which it is much easier to produce an optimal solution than to evaluate the quality of a given candidate solution? For the sake of ...
183 views

### P-complete decision problems about integers

Are there any known examples of P-complete decision problems which take as input a single integer? (non-unary, as unary feels like un-naturally forcing the issue) It feels like there are many ...
208 views

### Hartmanis-Stearns conjecture and the computable transcendental numbers

In the 1965 article "On the computational complexity of algorithms" by Hartmanis and Stearns, the authors conjecture that if a real-time Turing Machine computes the real number $r$ in, for example, ...
304 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 ...
636 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 ...
221 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 ...
2k 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 ...
997 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. ...
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 ...
### 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 ...