[[
wikihub
]]
Search
⌘K
Explore
People
For Agents
Sign in
Explore
People
For Agents
Sign in
@jemoka / Jemoka Knowledge Base / raw/concept/kbhbeyond_worst_case_analysis.md
Suggest edit
Cancel
Submit suggestion
Title
Name
Note
--- title: "Beyond Worst-Case Analysis" source: https://www.jemoka.com/posts/kbhbeyond_worst_case_analysis/ --- There is no polynomial time algorithm \(A\) such that for all 3CNF \(\varphi\), \(A\qty(\varphi)\) accepts if and only if \(\varphi\) is satisfiable. How do we relax this? we can say “for most” 3CNF formulas, which means that we have to name a distribution we can say to satisfy “most” \(\varphi\), meaning we can satisfy most clauses of \(\varphi\) allow more than poly-time (SoTA is at \(1.34\dots^{n}\)). PCP Theorem \(P \neq NP\) implies no polynomial time algorithm that finds \(x\) that satisfies \(99.9\%\) of clauses. In particular, no polytime algorithm that finds \(x\) that satisfies \(\geq \frac{7}{8} + \varepsilon\) fraction of the clauses. Min-Bisection Given a graph \(G\), split the vertices into two such that, with \(S \subseteq V\), \(| S | = \frac{n}{2}\), such that the number of edges \(s \leftrightarrow \bar{s}\) is minimized.