2022 Developer Survey is open! Take survey.

Tag Info

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 ...
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. ...
• 26.2k
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. ...
• 8,133

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 ...
• 1,704
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'...
• 23.5k

• 10.3k
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 ...

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 ...
• 342

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/...
• 21.3k

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 "...
• 10.7k
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 ...
• 7,350

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 ...
• 7,022
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":...

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 ...
• 7,643

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 ...
• 1,552
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 ...
• 10k
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 ...
• 2,718

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 ...
• 2,319

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: ...
• 1,133

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 ...
• 822

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 ...
• 10.8k
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 ...
• 937
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 ...