Timeline for Why are problems in P easy and other problems not
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 29, 2016 at 23:13 | review | Close votes | |||
| Apr 11, 2016 at 20:25 | |||||
| Mar 24, 2016 at 20:44 | comment | added | András Salamon | You seem to be essentially postulating a fixed amount of time that every problem instance must be decided in, then ask what happens to the number of decided instances as this time bound is doubled. Assuming that the language contains $2^{\Omega(n)}$ instances of size $n$, this just gives the usual definition of polynomial and exponential runtime. However, your definition will also conclude that all sparse and tally languages are hard, even trivial ones. So it might feel "engineering right" but it is mathematically wrong. | |
| Mar 24, 2016 at 13:09 | comment | added | Raphael | But that's exactly what's been asked and answered there! (Maybe you need to change your title.) | |
| Mar 24, 2016 at 11:52 | history | edited | Auberon | CC BY-SA 3.0 |
added 197 characters in body
|
| Mar 24, 2016 at 11:46 | comment | added | Auberon | No. I'm trying to ask if given informal, intuïtive definition is reasonable or not. I'm well aware of most common complexity classes and their definition/meaning | |
| Mar 24, 2016 at 10:56 | comment | added | Raphael | Community votes, please: is this a duplicate? | |
| Mar 24, 2016 at 10:26 | answer | added | Ariel | timeline score: 3 | |
| Mar 24, 2016 at 7:53 | history | asked | Auberon | CC BY-SA 3.0 |