# Tag Info

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


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

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

3

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 very little progress on general methods for this and that is essentially the entire subject of complexity theory. That being said, if you're more interested in ...

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