Suggest edit — Beyond Worst-Case Analysis

Title

Name

Note

---
title: "Beyond Worst-Case Analysis"
type: concept
source: https://www.jemoka.com/posts/kbhbeyond_worst_case_analysis/
confidence: high
status: active
---

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 &ldquo;for most&rdquo; 3CNF formulas, which means that we have to name a distribution we can say to satisfy &ldquo;most&rdquo; \(\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.