# Tag Info

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

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

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