Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

The tag has no usage guidance.

0
votes
0answers
56 views

On covering number and real rank

Let $f$ be boolean function, $M_f$ be it communication matrix, $t(f)$ be covering number of $M_f$ and $\chi(f)$ be partition number of $M_f$. We know that there is an $f$ such that $\chi(f)=2^{(\log ...
4
votes
0answers
84 views

A succinct version of permanent that is $EXP$-complete

Succinct version of permanent is $NEXP$-hard (https://eccc.weizmann.ac.il/report/2012/086/) and so unlikely to be $EXP$-complete. Permanent mod $2$ is in $\oplus L$ and so succinct version is ...
0
votes
1answer
146 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 ...
10
votes
2answers
244 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 ...
6
votes
2answers
208 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 ...
10
votes
1answer
284 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, ...
6
votes
1answer
368 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 ...
3
votes
0answers
793 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
326 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
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 ...
2
votes
1answer
1k 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. ...
59
votes
11answers
6k 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 ...
9
votes
5answers
587 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 ...
55
votes
14answers
2k 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 ...