[[
wikihub
]]
Search
⌘K
Explore
People
For Agents
Sign in
Explore
People
For Agents
Sign in
@jemoka / Jemoka Knowledge Base / raw/course/cs254/kbhsu_cs254_jan082025.md
Suggest edit
Cancel
Submit suggestion
Title
Name
Note
--- title: "SU-CS254 JAN082025" source: https://www.jemoka.com/posts/kbhsu_cs254_jan082025/ date: 2025-01-08 --- Notation New Concepts Church-Turing Thesis turing machine multi-tape TM theorem Time Complexity P NP: verifier formulation of NP non-determinism Important Results / Claims Turing Machine as a universal algorithm properties of turing machines Church-Turing thesis as local steps time hierarchy theorem Why stuff is great why TM is awesome why NP is awesome Questions Scratch Let \(L \in P\), and \(M\) be the polytime TM that decides \(L\). Define \(M’\) to be \(M\) with \(q_{\text{accept}}\) and \(q_{\text{reject}}\) swapped. Fact: \(M’\) decides \(\neg L\).