Questions tagged [examples]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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 ...
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-...
9
votes
5answers
635 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 ...
8
votes
1answer
382 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{...