Timeline for Is P=NP relevant to finding proofs of everyday mathematical propositions?
Current License: CC BY-SA 2.5
19 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 30, 2023 at 4:41 | comment | added | plm | I'm even more puzzled than you and now searching for some hints. The set of axioms most commonly used by mathematicians (ZFC for instance) are infinite (recursive), so there are infinitely many proofs of length 1. Even in finitely axiomatized theory playing with variables creates infinitely many proofs of given length. Thus what finite sets of proofs are we exploring nondeterministically (in NP) and checking (in P) exactly, for P vs NP to be relevant to common mathematical theorem proving ? I'm sure it is trivial but people who know don't seem to care about explaining what they mean. | |
| Nov 25, 2016 at 18:55 | comment | added | LSpice | I think that your "any proof of the [negation of the] proposition must have size at most polynomial in $n$" should be "some proof …"; we just need to find one proof of the statement or its negation. | |
| Mar 8, 2011 at 17:42 | answer | added | Timothy Chow | timeline score: 5 | |
| Jan 30, 2011 at 19:38 | history | edited | Adam | CC BY-SA 2.5 |
insert missing $T\vdash$
|
| Jan 30, 2011 at 19:38 | comment | added | Adam | @robin-adams: yes, indeed, thank you (edited to fix). | |
| Jan 29, 2011 at 18:39 | comment | added | user7247 |
Very pedantic point: I think you mean $T \vdash \phi$ or $T \vdash \neg \phi$' under 1, not $T \vdash \phi \vee \neg \phi$', which is true for all $\phi$ (if we're using classical logic).
|
|
| Dec 3, 2010 at 8:36 | comment | added | Lamine | I meant that computing capacities increase faster than the complexity of any problem in P (if the Moore's law is true). That allows some hope to solve this problem one day. | |
| Dec 3, 2010 at 6:04 | comment | added | Zen Harper | Lamine: "If A problem is in P, even if it has a large exponent and constant, it will be easy one day to compute." Sorry, I disagree: there's no hope if the constant or exponent is of size $3!!!!!!!!!!!!!!!!!!!!!!!!$ (iterated factorials), for example! | |
| Dec 2, 2010 at 22:22 | answer | added | gowers | timeline score: 18 | |
| Dec 2, 2010 at 21:09 | vote | accept | Adam | ||
| Dec 2, 2010 at 18:51 | answer | added | Andreas Blass | timeline score: 33 | |
| Dec 2, 2010 at 17:04 | answer | added | Ryan Williams | timeline score: 17 | |
| Dec 2, 2010 at 9:59 | comment | added | Lamine | The gap accorded by people between polynomial and exponential time can be justified by the Moore's law. It guesses that computing capacities increase exponentially (this may have a limit due to some silicon proprieties, but uses of other technologies to continue this increase can be expected). If A problem is in P, even if it has a large exponent and constant, it will be easy one day to compute. | |
| Dec 2, 2010 at 9:42 | answer | added | Someone | timeline score: 6 | |
| Dec 2, 2010 at 5:35 | comment | added | Oliver | I saw Martin Davis talk last year and he said something along the lines of he wouldn't be at all surprised if P=NP, but only because people tend to forget how horrid a polynomial time algorithm can be. Even if we had a P-time algorithm to check for proofs, it might not be of any practical use. | |
| Dec 2, 2010 at 0:37 | answer | added | David Harris | timeline score: 6 | |
| Dec 1, 2010 at 22:54 | answer | added | user5810 | timeline score: 2 | |
| Dec 1, 2010 at 22:49 | answer | added | Joseph O'Rourke | timeline score: 6 | |
| Dec 1, 2010 at 22:37 | history | asked | Adam | CC BY-SA 2.5 |