Timeline for Turing machine $\textbf{M}$, which ran in polynomial time, with an oracle
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 19 at 19:45 | comment | added | D.W.♦ | Please edit the post rather than leaving clarifications in the comments, so it will be clear for others, and so others don't have to read the comments to understand what is being asked. Thank you! | |
| Oct 19 at 10:02 | vote | accept | Xoxoxo | ||
| Oct 19 at 9:32 | answer | added | Nathaniel | timeline score: 2 | |
| Oct 19 at 8:52 | history | edited | Xoxoxo | CC BY-SA 4.0 |
edited body
|
| Oct 19 at 8:51 | comment | added | Xoxoxo | @D.W. it is satisfying assignment not "sufficient assignment". Sorry for typo. | |
| Oct 19 at 8:49 | comment | added | Xoxoxo | @D.W. "With an oracle approach to the SAT language" means that the deterministic Turing machine $\textbf{M}$ can make queries to an oracle, which can decide whether a given boolean formula (in this case, the 3SAT formula) is satisfiable or not in a single step, allowing $\textbf{M}$ to solve the problem efficiently by leveraging this oracle. | |
| Oct 19 at 4:51 | comment | added | D.W.♦ | What does "with an oracle approach to the SAT language" mean? What is a "sufficient assignment"? | |
| S Oct 18 at 19:40 | review | First questions | |||
| Oct 19 at 10:07 | |||||
| S Oct 18 at 19:40 | history | asked | Xoxoxo | CC BY-SA 4.0 |