2022 Developer Survey is open! Take survey.

Hot answers tagged

23 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. ...
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. ...
user avatar
  • 8,133
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 ...
user avatar
16 votes
Accepted

Would an optimal sorting network ever have to swap two numbers the "wrong" way

How do you decide what the "wrong way" is? Take the first wrong-way swap gate, and interchange the two wires going out of it (including all their associated gates) so that it's correct. This doesn'...
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}: \...
user avatar
13 votes

Humanifying computer-generated or computer assisted proofs

You are probably thinking of Gower's work with Ganesalingam, based on the latter's MSc dissertation (1). Gowers blogged about this in (2) and other places, and they've written a paper on the subject (...
user avatar
10 votes
Accepted

Correctness proofs of classic Paxos and Fast Paxos

Why can we assume that property CP held when acceptor a0 voted for v in round k? It seems that we are using mathematical induction, therefore, what are the basis, inductive hypothesis, and inductive ...
user avatar
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 ...
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 ...
user avatar
8 votes

Implications of unprovability of $P\neq NP$

As proved in this paper: http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/1991/CS/CS0699.revised.pdf If $P \neq NP$ can be shown to be independent of Peano Arithmetic, then NP has extremely-...
user avatar
  • 1,456
7 votes
Accepted

Would a proof assuming a physical law be considered sufficient?

It seems at least possible to me, but currently very unlikely. To sum up the below, it's because the current mathematical statement of (say) P vs NP is completely independent of any laws of physics, ...
user avatar
  • 7,022
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 $$ ...
user avatar
6 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 ...
user avatar
5 votes

Would a proof assuming a physical law be considered sufficient?

I like the question… but the answer is still "no", as other contributors have indicated. The question itself is metamathematical, which is why I like it. Mathematics and physics are different ...
user avatar
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/...
user avatar
  • 21.3k
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 "...
user avatar
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 ...
user avatar
  • 7,350
4 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 ...
user avatar
  • 7,022
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":...
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 ...
user avatar
  • 7,643
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 ...
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 ...
user avatar
  • 10k
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 ...
user avatar
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 ...
user avatar
  • 2,319
2 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: ...
user avatar
  • 1,133
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 ...
user avatar
  • 822
2 votes

Would a proof assuming a physical law be considered sufficient?

For example, I'm wondering what would happen if someone someday proved P != NP under the assumption of the second law of thermodynamics. the premise of the question is research-oriented but somewhat ...
user avatar
  • 10.8k
2 votes
Accepted

The random densification technique-JL lemma

It's not "obtained", but rather the bound the authors want on $\mathrm{Prob}[|u_1|\ge s]$. The Chernoff inequality says how large $s$ needs to be in order to guarantee the desired upper bound. As they ...
user avatar
  • 937
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 ...
user avatar

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