Hot answers tagged

22

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


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.


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

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


16

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


14

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

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


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

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

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-close-to-polynomial deterministic time upper bounds. In particular, in such a case, there is a $DTIME(n^{log^*(n)})$ algorithm that computes SAT correctly on ...


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

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

$ \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+...


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

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 $$ \newcommand{\SEMBTYPE}[1]{\ulcorner #1 \urcorner} \newcommand{\SEMB}[1]{\lbrack\!\lbrack #1 \rbrack\!\rbrack} \SEMB{\cdot} : L_1 \rightarrow L_2 $$ ...


6

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 pigeonhole principle in polynomial calculus (Razborov '98, IPS '99), and an exponential lower bound for the clique-colouring formula in cutting planes (Pudlák '99)....


5

Your construction does not work in general for the value of $k$ given. Say $x = 0$ and $y= (1, 0, \ldots, 0)$ (or any other standard basis vector). Then $f(x) = 0$ and $HDy$ is a vector with $1 + \log_2 d$ nonzero entries. We have $$ Pr[f(y) = 0] = \left(1 - \frac{1 + \log_2 d}{d}\right)^k \approx 1-O\left(\frac{k\log d}{d}\right), $$ for $k \ll d$. Of ...


5

I'd imagine that you'd have to go from first principles, by taking a TM that exhibits an arbitrary BPP algorithm and simulating it in P. This is how it is shown that $\mathsf{BPP} \in \Sigma_2 \cap \Pi_2$. In particular, you have to "derandomize" the space of random choices much like it is done for specific problems, where a small set of carefully chosen ...


5

Gödel's incompleteness theorem is really about provability given a theory with enough expressive power, you'll end up with some statement which can be true in some models, and false in others, hence not provable. In this case, if P vs NP can't be proved, if you believe that reality is a model of mathematics, P = NP or P $\neq$ NP must still be true in "our ...


5

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 epistemological universes, and never the twain shall meet. A mathematical universe is constructed of 1) definitions (like the integers) 2) axioms and 3) rules from ...


5

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/constructive mathematics with a very close meaning to what we call algorithm nowadays) goes back to at least Luitzen Egbertus Jan Brouwer. Note that Brouwer ...


5

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 "in parallel." The task is this: Input: An undirected graph. Task: Find a subgraph with maximum edge-connectivity. Note: What makes the task non-trivial is ...


4

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 as input, i.e., they cannot enforce any assumptions on the input graph, except that they observe that the minimal degree can be made arbitrarily large). (...


4

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 to allow length-increasing functions (that you need for PCP), you need a more powerful transducer model, for which undecidability quickly kicks in.


4

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": Let $X, Y \subseteq \{a\}^* \times \{b,c\}^*$ be rational relations defined by \begin{align*} X ={}& \{ (a^n, b^n c^k) \mid n,k \geq 0 \} \\ Y ={}& \{...


3

Regarding question 2, there are at least two other classes of matrices that give integral polehydra: the balanced and totally balanced matrices. When available, these properties are simpler to establish than total unimodularity. I'm not sure about question 1: your first paragraph seems to contain the answer, but after closer inspection I realize that total ...


3

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 edit sequence that proceeds left-to-right" or "we start by lining up the two words in columns vertically...." (Even if that feels obvious, can you ...


3

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 assumption is that the algorithm sorts via pairwise comparisons. Any such algorithm must make at least $\Omega(n\log n)$ such comparisons. This is because the ...


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