P problem

Alle Beslutningsproblem som er løselige i polynomisk tid.

---

Problemer i denne klassen omfatter rundt alle problemene vi har gått gjennom i pensum.

---

$$P\subseteq NP$$

Fordi alle problemer som kan løses i polynomisk tid, kan også verifiseres i polynomisk tid.

---

Vi kan definere kompleksitetsklassen $P$ ved Formelle språk

$$P=\{L\subseteq \{0,1{\}}^{\ast }:\text{det eksisterer en algoritme}A\text{som bestemmer}L\text{i polynomisk tid}\}$$

Viktig å merke seg

Dette er veldig tricky tldr; vi kan ha uendelig loops, og derfor er det viktig at alle strenger enten aksepteres eller avvises for at et språk skal være bestemt av en algoritme.

$\downarrow$ Lang forklaring $\downarrow$

En algoritmes aksepterte språk, $L$, er mengden av alle strenger som algoritmen aksepterer. Men, det betyr ikke nødvendigvis at en streng som ikke er i $L$ ($x\notin L$) avvises. Grunnen til dette er at det kan forekomme uendelige loops, som gjør at $x$ ikke bestemmes.

Derfor sier vi at et språk er bestemt av en algoritme dersom alle strenger i $L$ aksepteres, og alle strenger som ikke er i $L$ avvises.

---