Hot answers tagged

33

Consider the function (taken from here) $\qquad \displaystyle f(n) = \begin{cases} 1 & 0^n \text{ occurs in the decimal representation of } \pi \\ 0 & \text{else}\end{cases}$ Despite the looks, $f$ is computable by the following argument. Either $0^n$ occurs for every $n$ or there is a $k$ so that $0^k$ occurs but $0^{k+1}$ does not. We do not ...


26

This may not be exactly what you mean, but Seth Pettie and Vijaya Ramachandran's optimal minimum spanning tree algorithm is in some sense non-constructive. It is an open question whether there is a deterministic algorithm to compute minimum spanning trees in linear (meaning $O(n+m)$) time. Pettie and Ramachandran describe an algorithm that computes MSTs in ...


21

If P=NP, there must be polynomial-time algorithms for NP-complete problems. However, there might not be any algorithm that provably solves an NP-complete problem and provably runs in polynomial time.


21

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. Suppose Merlin can prove to Arthur that for a $k$-variable arithmetic circuit $C$, its value on all points in $\{0,1\}^k$ is a certain table of $2^k$ field ...


20

Your question might better be phrased, "How would complexity theory be affected by the discovery of a proof that P = NP is formally independent of some strong axiomatic system?" It's a little hard to answer this question in the abstract, i.e., in the absence of seeing the details of the proof. As Aaronson mentions in his paper, proving the independence of ...


20

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 Andrés Helfgott. His expository paper (https://arxiv.org/abs/1701.04372) and its translation (https://arxiv.org/abs/1710.04574) are all the support that is ...


20

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. (The neighboring cells are those among $A[i, j+1], A[i, j-1], A[i-1, j], A[i+1, j]$ that are present in the array.) So, for example, if $A$ is $$\begin{...


16

I thought about this problem again, and I think I have a full proof. It is a bit more tricky than what I anticipated. Comments are very welcome! Update: I submitted this proof on arXiv, in case this is useful to someone: http://arxiv.org/abs/1207.2819 $\DeclareMathOperator{\fp}{fp}$ $\DeclareMathOperator{\lp}{lp}$ $\newcommand{\fpp}[1]{\widehat{\fp{#1}}}$ $\...


16

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't change the fundamental circuit. It may introduce more wrong-way swap gates, but they're all later in the circuit. Now, you can keep doing this until you've ...


15

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 are not proof by contradiction, and therefore, in particular, are not instances of the pigeon-hole principle. There are also proofs by contradiction where the ...


13

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}: \mathcal{C} \subset \mathsf{NEXP} \wedge \mathcal{C} \not \subset \mathsf{P/poly})\implies \mathsf{NEXP} \not\subset \mathsf{P/poly}$$ is a statement that ...


13

Here are two examples. Some algorithms using the Robertson-Seymour theorem. The theorem states there exits a finite obstruction for each case, but does not provide a way to find such a finite set. Therefore, although we can prove that the algorithm exists, the explicit statement of the algorithm will depend on the finite obstruction set which we don't know ...


13

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 (3). There is other work in that direction, for example from the interactive proof assistant community. The most well-known example here might be the Isar ...


12

Another famous example is Hales' proof of Kepler's conjecture which had a very large computer aided component. From Wikipedia: In August 1998 Hales announced that the proof was complete. At that stage it consisted of 250 pages of notes and 3 gigabytes of computer programs, data and results.


11

This is a valid question, even though perhaps a little unfortunately phrased. The best answer I can give is this reference: Scott Aaronson: Is P versus NP formally independent. Bulletin of the European Association for Theoretical Computer Science, 2003, vol. 81, pages 109-136. Abstract: This is a survey about the title question, written for people who (...


11

I don't know where this was first proved, but since EdgeCover has an expression as a Boolean domain Holant problem, it is included in many Holant dichotomy theorems. EdgeCover is included in the dichotomy theorem in (1). Theorem 6.2 (in the journal version or Theorem 6.1 in the preprint) shows that EdgeCover is #P-hard over planar 3-regular graphs. To see ...


10

This is more of a meta answer in that it is a list of lists. The papers of Doron Zeilberger. He is a mathematician and his computer is listed at the coauthor Shalosh B. Ekhad on all papers where the computer played a part in deriving the results. Work of Georges Gonthier. He engineered a machine-checked proof of the four colour theorem and has been recently ...


10

You might be interested in Scott Aaronson's talk "Has There Been Progress on the P vs. NP Question?" (earlier version)


10

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 steps? You're looking at an instance of strong induction. In simple induction you assume the property holds for $n=m$ and prove it holds for $n=m+1$. In strong ...


9

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 source to $i$ and another edge of cost $s(i)$ from $i$ to sink. Also add edges from $i$ to $j$ of cost $t(i,j)$ for every pair of vertices $i$ and $j$. The cost of ...


8

Yes. At one point in (1), the complex-weighted counting graph homomorphism dichotomy theorem for any finite domain size, Cai, Chen, and Lu only prove the existence of a polynomial-time reduction between two counting problems via polynomial interpolation. I don't know of any practical value for such an algorithm. See Section 4 of the arXiv version. The ...


8

There is an optimal edit sequence in which the edit operations occur in order from left to right. There are only three options for the last edit operation: insert the last character of the target string, delete the last character of the source string, or replace the last character. Everything before the last edit operation must be optimal. See section 3.7 ...


7

Although there aren't any problems known to be $\mathsf{BPP}$-complete (and Sipser gave an oracle relative to which $\mathsf{BPP}$ doesn't have complete problems), one topic to look at here is pseudorandom generators. The existence of a good enough pseudorandom generator implies $\mathsf{BPP} = \mathsf{P}$. This isn't $\mathsf{BPP}$-complete, but it does ...


7

Some early results from late 80s: Fellows and Langston, "Nonconstructive tools for proving polynomial-time decidability", 1988 Brown, Fellows, Langston, "Polynomial-time self-reducibility: theoretical motivations and practical results", 1989 From the abstract of the second item: Recent fundamental advances in graph theory, however, have made available ...


7

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, so one would need to describe new models of computation that do depend on physics axioms. The key point that Peter Shor made in his comment is that CS theory ...


6

An example of an infinite family of problems (of questionable practical value) for which we can show: That for each problem there exists an algorithm to solve it. That there is no way to construct these algorithms (in general). In other words, a provably non-constructive proof. Our family of problem (from this question) for each Turing machine $M$: $L_{M}=...


6

As Timothy Chow explains, just knowing that a theorem is independent from a theory doesn't say much about the truth/falsity of that statement. Most non-experts confuse formal unprovability in a fixed theory (like $[ZFC][1]$) with impossibility of knowing that answer to the truth/falsity of the statement (or sometimes meaninglessness of the statement). ...


6

One example is the proof of non-existence of a projective plane of order 10. See The Search for a Finite Projective Plane of Order 10 and The Non-existence of Finite Projective Planes of Order 10.


6

First, you don't need to turn them into Turing machines, it is essentially the same as running a proof search algorithm. The logical complexity of the formula (which in the cases you have in mind are $\Pi^0_1$) has no effect on this, searching for proofs in any effective theory (like ZFC, for proof to make sense you have to fix a theory) can be done in a ...


6

$ \DeclareMathOperator{\inv}{inv} \DeclareMathOperator{\maj}{maj} $ This is not an example of what you are asking for, but it suggests how such an example can come about. Some combinatorial identities can be encoded as identities about polynomials of bounded degree $d$. If the polynomials are univariate, to prove the identity it is enough to verify it on $d+...


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