Timeline for Do the NP: find the largest clique
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 1, 2017 at 6:23 | comment | added | miles | I believe this is O(1.414^n). You can see worse performance when the input is a complete graph. | |
| Sep 1, 2017 at 5:19 | comment | added | rus9384 | @FelixPalmen, of course it would, but it can't be heuristics for the proof. | |
| Sep 1, 2017 at 5:10 | comment | added | Felix Palmen | @rus9384 "it can't" would need proof --- while finding a polynomial algorithm here would be instant proof that P=NP (the problem is NP complete) :) | |
| Aug 31, 2017 at 18:16 | comment | added | rus9384 | @FelixPalmen, or it can' t. Anyway, for million one of two statements must be proved. | |
| Aug 31, 2017 at 11:13 | comment | added | Felix Palmen |
Adding to that, to be worth a million, the n may only appear in the bases :)
|
|
| Aug 31, 2017 at 10:15 | comment | added | rus9384 | @EriktheOutgolfer, you are wrong, there are algorithms which have O(1.1888ⁿ) runtime. | |
| Aug 31, 2017 at 8:55 | comment | added | Erik the Outgolfer | And what complexity does this have? If it's anything lower than O(2ⁿ) then it deserves $1,000,000. | |
| Aug 31, 2017 at 8:21 | history | answered | miles | CC BY-SA 3.0 |