Questions tagged [examples]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
69
votes
13answers
8k views

Common false beliefs in theoretical computer science

This post is inspired by the one in MO: Examples of common false beliefs in mathematics. Since the site is designed for answering research level questions, examples like $\mathsf{NP}$ stands for non-...
0
votes
1answer
51 views

Do such instances always admit a 3D matching?

I want to know whether the following kinds of special instances of the 3D Matching problem are ``yes" instances, i.e., admit a 3D matching. We are given 3 sets $A,B,C$ containing $m$ elements ...
57
votes
18answers
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 ...
-4
votes
1answer
120 views

Example of decidable NP-hard problem that is not NP-complete [closed]

I am looking for an example of a decision problem which fulfills the following conditions: 1. It is decidable 2. It is NP-hard 3. It is not NP-complete All my search attempts yielded examples that ...
8
votes
1answer
381 views

On theoretical aproaches for solving $\mathsf{SAT}$ in special cases

In what cases $\mathsf{SAT}$ can be solved in polynomial time? I know two cases: $2$-$\mathsf{SAT}$ and Horn-$\mathsf{SAT}$. Question 1: Is there a reference with algorithms for solving $\mathsf{...
8
votes
0answers
228 views

A canonical complete problem for EXP and NEXP in terms of formulae

3SAT is a complete problem for NP. TQBF is a complete problem for PSPACE. Is there direct way to define canonical complete problems for EXP and NEXP in terms of boolean formulae? I have only seen ...
1
vote
1answer
153 views

Uniqueness of the distribution maximizing the channel capacity

Setting: We look at a discrete memoryless channel which takes an input probability distribution acting over symbols in $\mathcal{X}$ to an output probability distribution over symbols in $\mathcal{Y}$....
4
votes
0answers
94 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
234 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
275 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
220 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
318 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
439 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
926 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 ...
6
votes
0answers
540 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
1answer
2k 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. ...
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 ...
9
votes
5answers
634 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 ...