Hot answers tagged

27 votes
Accepted

What's the status of Babai's Graph isomorphism result?

Aggregating comments by Thomas Klimpel, Sasho Nikolov and Mohammad Al-Turkistany into a community answer: The correction (and hence the quasi-polynomial result) was immediately supported by Harald ...
22 votes
Accepted

How is the MA version of SETH proven to be false?

You can find a preprint by following this link http://eccc.hpi-web.de/report/2016/002/ EDIT (1/24) By request, here is a quick summary, taken from the paper itself, but glossing over many things. ...
Ryan Williams's user avatar
20 votes
Accepted

Examples of algorithms and proofs that seem correct, but aren't

2D local maximum input: 2-dimensional $n \times n$ array $A$ output: a local maximum -- a pair $(i,j)$ such that $A[i,j]$ has no neighboring cell in the array that contains a strictly larger value. ...
Neal Young's user avatar
  • 10.1k
17 votes

Possible to do Complexity theory with only counting and Pigeonhole

If you are looking for non-pigeon-hole type arguments, then there is good news: they exist! The pigeon-hole principle is a certain template for proof by contradiction. There are concepts in TCS which ...
Lieuwe Vinkhuijzen's user avatar
14 votes

Proofs, Barriers and P vs NP

Contrary to some claims earlier in this thread, algebrization in the sense of Aaronson & Wigderson is not known to subsume relativization. For example, $$\tag{$\dagger$}(\exists \mathcal{C}: \...
Barış Aydınlıoğlu's user avatar
12 votes

Implications of unprovability of $P\neq NP$

As proved in the paper "On The Independence of P Versus NP" by S. Ben-David and S. Halevi: If $P \neq NP$ can be shown to be independent of Peano Arithmetic, then NP has extremely-close-to-...
Avi Tal's user avatar
  • 1,606
9 votes
Accepted

Proof that the graph optimization problem is NP-hard

This problem is in P, it can be reduced to the Minimum cut problem. The graph construction is as follows - Add a source and a sink vertex. For each vertex $i$, add an edge with cost $w(i)$ from ...
saisandeep's user avatar
9 votes
Accepted

Construction of arbitrary functions with exponential-size $MODp \circ MODq$ circuits

$\def\M#1{\mathrm{MOD}_{#1}}\def\F#1{\mathbb F_{#1}}$I don’t know of a reference, but here is one way how to prove the result. I’ll do it in three stages, each using one new idea: (1) multilinear ...
Emil Jeřábek's user avatar
7 votes
Accepted

Document references describing weaknesses for cutting planes and algebraic proof system?

For each of these proof systems we know that there are some formulas where the shortest proof needs to have exponential length. Some of the earliest examples are an exponential lower bound for the ...
notautogenerated's user avatar
6 votes

How to prove relations between "classes" of types?

One approach to such questions is via encodings. Say you have a language $L_1$ and a language $L_2$ and you want to show that they are somehow "the same", you can do this by finding an encoding $$ ...
Martin Berger's user avatar
6 votes
Accepted

Conversion between NP certificates

For general $L\in\mathrm{NP}$, this is equivalent to $\mathrm{FP=TFNP}$, hence likely false: On the one hand, if $V$ and $V'$ are verifiers of $L$, then “given $x$ and $u$ such that $V(x,u)$, find $u'$...
Emil Jeřábek's user avatar
5 votes

Proof of Levenshtein distance

I looked into this last year while teaching. The other answers, including Prof. Erickson's excellent book, feel incomplete, because they handwave a step along the lines of "there is an optimal ...
usul's user avatar
  • 7,615
5 votes

Where is the quote "Informal proofs are algorithms, formal proofs are code" from?

He doesn't cite any references for it and Google doesn't return any results so I don't think he is really quoting from anywhere. The idea that a proof is a "construction" (a term in intuitionistic/...
Kaveh's user avatar
  • 21.6k
5 votes

Examples of the value of proofs for algorithms

Here is a natural problem from graph theory where the proof and the algorithm are closely intertwined. In my view, one can discover this algorithm only via thinking about the proof and the algorithm "...
Andras Farago's user avatar
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
4 votes
Accepted

Are equalizers of regular functions always regular languages? (My guess is no because PCP, but...)

The problem is in your assumption that rational relations are closed under intersection. The following counter-example is taken from Example 2.5 in Berstel's "Transductions and Context-Free Languages":...
Ulrik Rasmussen's user avatar
4 votes

Are equalizers of regular functions always regular languages? (My guess is no because PCP, but...)

If you use Mealy machines, it forces your functions to be length-preserving, and therefore you cannot encode PCP with them. Your regularity theorem holds with length-preserving functions. If you want ...
Denis's user avatar
  • 8,678
4 votes
Accepted

Complexity of counting the number of edge covers of a graph

After some more literature search, it appears that the complexity of counting the edge covers in a graph was shown to be #P-complete in bordewich2008path, Appendix A.1. (This assumes arbitrary graphs ...
a3nm's user avatar
  • 9,232
3 votes

Proof of the pumping lemma for context-free languages using pushdown automata

When discussing this problem with Géraud Sénizergues, he pointed me this paper by Sakarovitch that already proves this result. The proof seems to date back to this paper by Ogden. References: ...
Lamine's user avatar
  • 1,138
3 votes

Formally proving no algorithm exists

What you are asking for is methods in proving lower bounds on the computational complexity (measured in space, time, etc) of given computational problems, and the answer is mostly that we have made ...
Samuel Schlesinger's user avatar
3 votes
Accepted

Formally proving no algorithm exists

See this lower bound for sorting, for example: http://planetmath.org/lowerboundforsorting You typically need to assume something about the algorithm's access to the input data. In this case, the ...
Aryeh's user avatar
  • 10.5k
3 votes
Accepted

How hard is this combinatorial optimisation problem?

This problem can be solved with dynamic programming in pseudo-polynomial time (proof below). Therefore, it is not possible to show that this problem is strongly NP-hard (unless P=NP). First, let's ...
Mikhail Rudoy's user avatar
3 votes

Sources that prove solving 2-SAT with DP takes linear time

It is a very basic exercise for undergraduate/graduate courses in Theoretical computer Science, and I think books avoid giving the solution so that students do not copy it without understanding. Here ...
J..y B..y's user avatar
  • 2,766
2 votes

Paxos made simple, invariant P2c

We prove it ($P2^c \implies P2^b$) by strong induction (wiki). This proof has actually been given in the "Paxos Made Simple" paper (see the arguments between $P2^b$ and $P2^c$). I re-organize it in ...
hengxin's user avatar
  • 2,329
2 votes

An Interactive Proof of God's Number?

Determining that $20$ is the diameter (God's number) of the Rubik's Cube Group $G$ under the half-turn metric with Singmaster generating set $s=\langle U, U', U^2, D, D', D^2,\cdots\rangle$ was a ...
Mark S's user avatar
  • 1,083
2 votes
Accepted

Formally prove that the loops of this sorting algorithm will terminate

Since the loop variables $i$ and $j$ are not modified in the loop body, you can compute the exact number of iterations. The inner loop is executed $n-i$ times in each iteration of the outer loop, so ...
Mark Dettinger's user avatar
2 votes

Examples of the value of proofs for algorithms

I see several advantages of mastering the proof of correctness and complexity of an algorithm. I list them below and illustrate with a concrete example. I tried to stay in the domain of classical ...
holf's user avatar
  • 2,174
2 votes

Examples of the value of proofs for algorithms

A practical answer: In my career I encountered a few scenarios, some with my direct involvement, where I had to prove that my algorithm performs just as good as the currently best known possible. ...
Avi Tal's user avatar
  • 1,606
2 votes

Proving proof system properties within the proof system itself?

There is no loop. The purpose of a formal system is to make reasoning principles explicit and to explain more precisely how reasoning works. The word "foundation" in "foundations of ...
Andrej Bauer's user avatar
  • 28.8k
2 votes
Accepted

Proving proof system properties within the proof system itself?

The first problem is what does is even mean that a propositional proof system can prove its own properties: there is a serious discrepancy of the languages, because the propositional proof system can ...
Emil Jeřábek's user avatar

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