Timeline for Can every Turing Machine be translated into a SAT formula?
Current License: CC BY-SA 4.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 13, 2019 at 6:56 | comment | added | dkaeae | Indeed. It seems the (only?) requirement for the reduction to work is that the time of $M$ is bounded by a computable function. (This implies, among other things, that $M$ always halts on every input.) | |
| Jun 12, 2019 at 18:46 | vote | accept | MLStudent | ||
| Jun 12, 2019 at 18:46 | |||||
| Jun 12, 2019 at 18:46 | comment | added | MLStudent | Thanks! I will edit my question to add: Can we define a reduction, which has a running time somehow bounded by the input length (not necessarily by a polynomial though), but still outputs a sat formula that is satisfiable iff $M$ accepts $x$? I think in this case, Yuval's answer holds, correct? | |
| Jun 12, 2019 at 12:24 | history | answered | dkaeae | CC BY-SA 4.0 |