Timeline for Succinct circuits and NEXPTIME-complete problems
Current License: CC BY-SA 4.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 11, 2019 at 22:16 | comment | added | user36212 | (1) Any time you have a problem which is (class)-hard on a given set of inputs, and the set is sparse, you can boost hardness. If the set is sparse and also you have an efficient way to represent them, this boosting is something you can control (in your example, going from NP to NEXP and not to something even higher). (2) It's called padding, and it's a nice trick to get intermediate or 'tuned' problems from ones which are harder than you wanted. | |
| Mar 11, 2019 at 22:14 | comment | added | ACGT | That is interesting, is this the same as 1-hot-encoding? Could you give an example hot to use such an encoding trick please? Thank you! | |
| Mar 11, 2019 at 22:12 | comment | added | Wojowu | For 2), if you use unary encoding of numbers, then many NP-complete problems become easy. | |
| Mar 11, 2019 at 22:06 | history | asked | ACGT | CC BY-SA 4.0 |