Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more
16 votes
Accepted

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

Concerning Question 1, there have mainly been two lines of work to find tractable restrictions of SAT. The first one that you are already familiar with is to restrict the types of the clauses that ...
holf's user avatar
  • 2,174
11 votes

List of nice non-context-free languages

If I had to summarize the capabilities/limitations of CF languages I would say: they can pair "things" but two distinct pairings cannot overlap they can "count" but only linearly (...
Marzio De Biasi's user avatar
7 votes

Common false beliefs in theoretical computer science

Superpolynomial time complexity cannot be in P. While this appears easy to believe, it is actually a false belief. Formally, we may think that if $f(n)$ is a superpolynomial function, then ${\mathsf {...
6 votes

List of nice non-context-free languages

Two simple examples of non-context-free languages are PRIMES $= \{ a^p \mid p \text{ prime} \}$ and POWERS $= \{ a^{2^n} \mid n\ge 0 \}$. One can prove that they are not context-free by the pumping ...
Noam Zeilberger's user avatar
5 votes

Common false beliefs in theoretical computer science

"When a problem is algorithmically undecidable, it means that it has a definite provable answer (yes or no) on all instances, but no unique algorithm is capable to reach this answer uniformly on ...
4 votes
Accepted

Uniqueness of the distribution maximizing the channel capacity

This conjecture is false. Here is a counterexample. Suppose we have a binary symmetric channel: $x_1 \rightarrow y_1$ with probability $1-\epsilon$ and $y_2$ with probability $\epsilon$, $x_2 \...
Peter Shor 's user avatar
3 votes

List of nice non-context-free languages

You can group non-context-free languages into groups depending on what lemma you use to show that they are not context-free. Noam already mentioned the pumping lemma in his answer, let me mention the ...
domotorp's user avatar
  • 14k
3 votes
Accepted

Example of decidable NP-hard problem that is not NP-complete

You can trivially consider NEXP-complete problems and they satisfy all 3 conditions that you're looking for. And by the Time Hierarchy Theorem, NP is strictly in NEXP.
nathan34's user avatar
2 votes
Accepted

Do such instances always admit a 3D matching?

How about the following counter-example? $m=2$, $n=4$. $A=\{a_1,a_2\}$, $B=\{b_1,b_2\}$, $C=\{c_1,c_2\}$. $T=\{(a_1,b_1,c_1), (a_1,b_2,c_2), (a_2,b_1,c_2), (a_2,b_2,c_1)\}$. With the partition $A\cup ...
Tassle's user avatar
  • 881
2 votes

Where and how did computers help prove a theorem?

A paper of mine with Gupta and Kumar titled On a bidirected relaxation for the MULTIWAY CUT problem was also based on running experiments. In fact we were trying to prove the converse of what we ended ...
1 vote

List of nice non-context-free languages

The following is kind of a variant of the examples already given, but I believe it is sufficiently different that is worth mentioning. $L=\{a^n b^m a^n b^m\mid n,m\in \mathbb{N}\}$ Proof by using the ...
Pavlos M.'s user avatar
1 vote

Where and how did computers help prove a theorem?

My recent paper with Karthik Chandrasekharan titled Hypergraph $k$-cut in deterministic polynomial time was based on extensive computational experiments. We explored different conjectures and ...
1 vote

Where and how did computers help prove a theorem?

Some recent results in state complexity were found with the help of systematic brute-force search for worst-case examples. This is doable because there are not too many deterministic finite automata ...
1 vote

Where and how did computers help prove a theorem?

In 2018, Aubrey de Grey found a 1581-vertex, non-4-colourable unit-distance graph. This gives a lower bound of five for the famous Hadwiger-Nelson problem. He used a computer to verify that the graph ...

Only top scored, non community-wiki answers of a minimum length are eligible