---
title: "Hesaplama Karmaşıklığı: P, NP, NP-Tamlık"
subtitle: "Bütün bir alan tek derste — sınıf hiyerarşisi, halting, şanslı algoritma ve certificate, reduction ile zorluk kanıtı"
---
::: {.callout-note title="Oturum bilgisi"}
- **Demaine'in videosu:** [YouTube — Lecture 19: Complexity](https://www.youtube.com/watch?v=JbafQJx1CIA) (≈59 dk)
- **OCW sayfası:** [MIT 6.006 Lecture 19: Complexity](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/resources/mit6_006s20_lec19/)
- **Seri:** MIT 6.006 — Introduction to Algorithms (Spring 2020) — Ders 28 (L19)
- **Hoca:** Erik Demaine (hesaplama karmaşıklığı; bütün bir alan tek derste)
- **Okuma süresi:** ≈28 dk
> Bu ders **ödevlerde işlenmedi**; final'de yalnız **TANIMLAR** test edilir (Ders 31'in retrospektif notu). Önceki dört DP dersinden (Ders 23-27) sonra perspektif tersine döner: artık "nasıl iyi çözeriz?" değil, "**neden iyi çözemeyiz?**" (alt sınır) sorusu merkezdedir. Subset sum'ın (Ders 27) "evet kolay, hayır zor" gözlemi tam buraya, **NP**'ye bağlanır.
:::
## Bu Derste Ne Var? {#sec-bu-derste-ne-var-d28}
Bütün bir alanı tek derste: **hesaplama karmaşıklığı (computational complexity)** (Erik Demaine). Algoritmalar "nasıl iyi çözeriz?" derken, karmaşıklık "**neden iyi çözemeyiz?**" (alt sınır) der. Buradaki ölçek **polinom vs üstel** ($n$ vs $n \log n$ değil).
> *"cover an entire field, which is computational complexity."* — Demaine, 0:19
Şaşırtıcı sonuç: **çoğu problemin hiçbir algoritması yoktur.**
> *"most problems actually have no algorithm."* — Demaine, 1:32
Üç ana fikir:
1. **Sınıf hiyerarşisi** — $P \subseteq NP \subseteq EXP \subseteq R$; halting problem $R$ dışında (uncomputable); çoğu problem çözülemez.
2. **NP** — "şanslı algoritma" (hep doğru tahmin) veya "certificate ile polinom-zamanda doğrulanabilir".
3. **NP-tamlık + reduction** — bir problemi bilinen-zor bir probleme indirgeyerek zorluğunu kanıtla.
```{mermaid}
%%| label: fig-concept-map
%%| echo: false
%%| fig-cap: "Ders 28'in (L19) kavram haritası: kök = Hesaplama Karmaşıklığı (Demaine) — bütün bir alan tek derste, perspektif tersine döner ALT SINIR tarafı yani neden iyi çözemeyiz. Dört dal — (1) Sınıf hiyerarşisi P alt küme NP alt küme EXP alt küme R: P polinom zamanda CÖZÜLEBİLİR verimli örnek negatif çevrim tespiti Bellman-Ford; NP polinom zamanda DOĞRULANABİLİR örnek Tetris ve subset sum; EXP üstel zamanda çözülebilir örnek n çarpı n satranç; R herhangi sonlu zamanda decidable; P ile EXP farkı KESİN ama P ile NP eşit mi AÇIK bir milyon dolarlık problem. (2) Halting problem R DIŞI uncomputable: verilen bir program durur mu sorusu, mükemmel bir hata bulucu olurdu ama imkânsızdır hiçbir algoritma karar veremez. (3) Çoğu problem çözülemez SAYMA argümanı: program sonlu bit dizisi yani doğal sayı SAYILABİLİR countable, karar problemi her girdi için evet hayır yani sonsuz bit dizisi yani sıfır bir aralığında reel sayı SAYILAMAZ uncountable, reel kat kat fazla yani problemlere yetecek program YOK yani çoğu problem çözülemez. (4) NP sınıfı iki eşdeğer tanım artı NP-tamlık: Tanım bir ŞANSLI algoritma tahmin yapabilir ve bir evet yolu varsa hep doğru tahmin eder; Tanım iki DOĞRULAYICI girdi artı certificate alıp polinom zamanda kontrol eder, ASİMETRİ evet ispatlanabilir hayır değil; NP-hard NP kadar zor alt sınır, NP-complete NP kesişim NP-hard NP'nin en zoru Tetris TSP üç-SAT; REDUCTION bilinen-zor problemi hedefe indirge örnek üç-partition oku Tetris zorluk kanıtı. Birleştirici tema: problemler zorluk ekseninde sınıflanır P verimli çözülebilir alt küme NP verimli doğrulanabilir alt küme EXP alt küme R, çoğu problem R'nin bile dışındadır halting gibi uncomputable, NP-tam problemler NP'nin en zorudur ve bir problemi NP-tam bir probleme indirgeyerek P eşit değil NP ise verimli çözülemez kanıtlanır, şans engineer edilemez modern güvenliğin dayanağıdır."
flowchart TD
A["Ders 28 (L19): Hesaplama Karmaşıklığı — P, NP, NP-Tamlık (Demaine)"] --> SH["Sınıf hiyerarşisi — P ⊆ NP ⊆ EXP ⊆ R"]
SH --> SHa["P çözülebilir · NP doğrulanabilir · EXP üstel · R sonlu<br/>P ≠ EXP KESİN; P =? NP AÇIK (1 M$)"]
A --> HP["Halting problem — R DIŞI (uncomputable)"]
HP --> HPa["program durur mu? mükemmel hata bulucu olurdu<br/>ama imkânsız — hiçbir algoritma karar veremez"]
A --> CP["Çoğu problem çözülemez — SAYMA argümanı"]
CP --> CPa["program = sonlu bit = ℕ (sayılabilir)<br/>problem = sonsuz bit = ℝ (sayılamaz) → program YOK"]
A --> NP["NP — iki tanım + NP-tamlık + reduction"]
NP --> NPa["şanslı algoritma ≡ certificate doğrulayıcı; ASİMETRİ<br/>NP-hard alt sınır; reduction: 3-partition → Tetris"]
classDef root fill:#fef3c7,stroke:#b45309,stroke-width:3px,color:#1f2937
classDef branch fill:#f3f4f6,stroke:#374151,stroke-width:2px,color:#1f2937
classDef leaf fill:#ffffff,stroke:#9ca3af,stroke-width:1px,color:#1f2937
class A root
class SH,HP,CP,NP branch
class SHa,HPa,CPa,NPa leaf
```
```{python}
#| echo: false
# ============================================================================
# SETUP — 6.006 Ders 28 (L19) Hesaplama Karmaşıklığı motoru
# (_engine.py D28 bölümü + bağımlılıkları INLINE GÖMÜLÜ — import YOK,
# brief: setup hücresine göm). Fonksiyonlar:
# bfs → ağırlıksız SP (L9); R1/R2 reduction tanığı.
# relax_edge / dag_relaxation → DAG SP gevşetme (L16); R3 negatifle köprüsü.
# ChangeablePQ / dijkstra → ağırlıklı SP (L19/Dijkstra); R1/R2 tanığı.
# build_weighted_dag_example → R3 (en-uzun → en-kısa) DAG örneği.
# reduce_unweighted_to_weighted / reduce_integer_to_unweighted
# → §9 Reduction-1 (w=1) ve Reduction-2 (kenar-bölme).
# dag_longest_path / brute_dag_longest → §9 Reduction-3 (negatifle) + üstel tanık.
# subset_sum / subset_sum_certificate / brute_subset_sum / build_subset_example
# → karar problemi (D27 köprüsü) + 2ⁿ bitmask tanığı + ebeveyn-izi certificate.
# verify_subset_certificate → §6 NP Tanım-2 doğrulayıcısı (POLİNOM kontrol).
# Slate+Amber viz sabitleri (_viz.py COL_*) + apply_style. Bu hücre gizli
# (#| echo: false).
#
# Aşağıdaki TÜM figür hücreleri burada tanımlanan fonksiyonları IMPORT ETMEDEN
# kullanır (dosyadan import YOK). Notion'daki öğretim içeriği (görünür anlatı)
# bu motorun kavram seviyesidir; burada tam, deterministik, test edilmiş sürüm yaşar.
#
# NOT: matplotlib.use("Agg") ÇAĞRILMAZ — Quarto'nun inline figür-yakalama
# backend'ini ezer (plt.show() 0 figür üretir).
# ============================================================================
import math
from collections import deque
import matplotlib.pyplot as plt
from matplotlib.patches import FancyBboxPatch, FancyArrowPatch, Circle, Polygon
# ---------------------------------------------------------------------------
# _viz.py — Slate+Amber stil sabitleri (HEX birebir) + apply_style
# ---------------------------------------------------------------------------
COL_PRIMARY = "#374151" # slate-700 — birincil çizgi/çerçeve
COL_ACCENT = "#f59e0b" # amber-500 — vurgu
COL_TEXT = "#1f2937" # slate-800 — metin
COL_BG = "#f3f4f6" # slate-100 — arka plan / kutu dolgusu
COL_AMBER_700 = "#b45309" # bağlantı/okunur kontrast
COL_AMBER_600 = "#d97706" # koyu amber
COL_AMBER_300 = "#fcd34d" # açık amber
COL_AMBER_100 = "#fef3c7" # en açık amber (dolgu)
COL_SLATE_500 = "#6b7280" # orta slate — ikincil metin
COL_SLATE_400 = "#9ca3af" # soluk slate — pasif kenar / izgara
COL_WHITE = "#ffffff"
# "HAYIR" / yanlış-cert / uncomputable için kırmızımsı tonlar (uyarı rengi)
COL_RED = "#b91c1c" # red-700 — yanlış-cert çarpısı / "kanıt yok"
COL_RED_BG = "#fee2e2" # red-100 — açık kırmızı dolgu
def apply_style(ax):
"""Bir eksene tutarlı Slate+Amber görünümü uygular (curve figürleri için)."""
ax.set_facecolor(COL_WHITE)
ax.grid(True, alpha=0.25, color=COL_SLATE_400, linewidth=0.8)
for spine in ax.spines.values():
spine.set_color(COL_SLATE_400)
ax.tick_params(colors=COL_TEXT)
ax.title.set_color(COL_TEXT)
ax.xaxis.label.set_color(COL_TEXT)
ax.yaxis.label.set_color(COL_TEXT)
return ax
INF = float("inf")
# ---------------------------------------------------------------------------
# _engine.py L9 §8 — BFS (ağırlıksız SP); R1/R2 reduction tanığı
# ---------------------------------------------------------------------------
def bfs(adj, s):
"""BFS (L9 §8): kaynaktan katman katman; (delta, parent) döndürür.
'Henüz görülmemiş' kontrolü ilk (= en kısa) uzaklığı sabitler. O(V+E)."""
delta = {s: 0}
parent = {s: None}
queue = deque([s])
while queue:
u = queue.popleft()
for v in adj[u]:
if v not in delta: # henüz görülmemiş
delta[v] = delta[u] + 1
parent[v] = u
queue.append(v)
return delta, parent
# ---------------------------------------------------------------------------
# _engine.py L16 §8-10 — DAG SP gevşetme; R3 (negatifle) köprüsü
# ---------------------------------------------------------------------------
def relax_edge(d, weight, u, v):
"""Kenar gevşetme (L16): üçgen eşitsizliği ihlali varsa tahmini düşür."""
if d[u] + weight[(u, v)] < d[v]:
d[v] = d[u] + weight[(u, v)]
return True
return False
def dag_relaxation(adj, weight, s, topo_order):
"""DAG relaxation (L16): d=∞, d[s]=0; topolojik sırada her u'nun çıkış
komşularını gevşet. O(V+E)."""
d = {v: INF for v in adj}
d[s] = 0
for u in topo_order:
for v in adj[u]:
relax_edge(d, weight, u, v)
return d
def build_weighted_dag_example():
"""L16 çalışılan örneğine uyumlu DAG: topolojik sıra a,b,e,f,g,h,d,c;
kaynak e. Beklenen δ(e,·): e=0, f=3, g=5, h=6, d=3, c=8; a=b=+∞."""
adj = {"a": ["b"], "b": [], "e": ["f"], "f": ["h", "g"],
"g": ["h", "d"], "h": [], "d": ["c"], "c": []}
weight = {("a", "b"): 1, ("e", "f"): 3, ("f", "h"): 8, ("f", "g"): 2,
("g", "h"): 1, ("g", "d"): -2, ("d", "c"): 5}
topo = ["a", "b", "e", "f", "g", "h", "d", "c"]
return adj, weight, topo
# ---------------------------------------------------------------------------
# _engine.py L19 §5-6 — ChangeablePQ + Dijkstra (ağırlıklı SP); R1/R2 tanığı
# ---------------------------------------------------------------------------
class ChangeablePQ:
"""Değiştirilebilir min-öncelik kuyruğu (L19 §5): binary min-heap +
id→konum sözlüğü. build O(n), delete_min / decrease_key O(log n)."""
def __init__(self, items=()):
self.a = [(k, i) for i, k in items] # (key, id)
self.pos = {item[1]: idx for idx, item in enumerate(self.a)}
for j in range(len(self.a) // 2 - 1, -1, -1): # heapify O(n)
self._sift_down(j)
def __len__(self):
return len(self.a)
def _swap(self, i, j):
self.a[i], self.a[j] = self.a[j], self.a[i]
self.pos[self.a[i][1]] = i
self.pos[self.a[j][1]] = j
def _sift_up(self, j):
while j > 0:
p = (j - 1) // 2
if self.a[p][0] <= self.a[j][0]:
break
self._swap(p, j)
j = p
def _sift_down(self, j):
n = len(self.a)
while True:
l, r, small = 2 * j + 1, 2 * j + 2, j
if l < n and self.a[l][0] < self.a[small][0]:
small = l
if r < n and self.a[r][0] < self.a[small][0]:
small = r
if small == j:
return
self._swap(j, small)
j = small
def delete_min(self):
"""En küçük anahtarlı id'yi çıkar. O(log n)."""
top_key, top_id = self.a[0]
last = self.a.pop()
del self.pos[top_id]
if self.a:
self.a[0] = last
self.pos[last[1]] = 0
self._sift_down(0)
return top_id, top_key
def decrease_key(self, vid, new_key):
"""id'li öğenin anahtarını DÜŞÜR (cross-link ile konumu O(1) bul). O(log n)."""
j = self.pos[vid]
assert new_key <= self.a[j][0], "decrease_key yalnız düşürür"
self.a[j] = (new_key, vid)
self._sift_up(j)
def dijkstra(adj, weight, s):
"""Dijkstra (L19 §6): en yakını çıkar, kenarlarını gevşet, decrease_key
ile güncelle. Ağırlıklar ≥ 0 ŞART."""
d = {v: INF for v in adj}
d[s] = 0
Q = ChangeablePQ((v, d[v]) for v in adj)
while len(Q):
u, _ = Q.delete_min()
for v in adj[u]:
if d[u] + weight[(u, v)] < d[v]:
d[v] = d[u] + weight[(u, v)]
Q.decrease_key(v, d[v])
return d
# ---------------------------------------------------------------------------
# _engine.py D27 (L18) §4-5 — Subset sum: karar problemi (D27 köprüsü)
# ---------------------------------------------------------------------------
def subset_sum(A, T):
"""Subset sum memoized DP (L18 §5): x(i, t) = A[i:] sonekinin bir alt
kümesi t'ye toplanır mı? karar problemi → min/max değil OR. O(n·T)
PSEUDOpolinom. Döndürür: (cevap, memo)."""
n = len(A)
memo = {}
def x(i, t):
if (i, t) in memo:
return memo[(i, t)]
if i == n:
r = (t == 0)
else:
r = x(i + 1, t) # aᵢ dışarıda
if not r and A[i] <= t:
r = x(i + 1, t - A[i]) # aᵢ içeride
memo[(i, t)] = r
return r
return x(0, T), memo
def subset_sum_certificate(A, T):
"""'Evet' certificate'i (L18 §5 + §4 asimetri): ebeveyn iziyle T'ye
toplanan alt kümeyi geri kur; cevap 'hayır' ise None (kısa kanıt YOK —
NP asimetrisi)."""
ok, _ = subset_sum(A, T)
if not ok:
return None
subset, t = [], T
n = len(A)
for i in range(n):
if subset_sum(A[i + 1:], t)[0]: # aᵢ'siz devam mümkünse atla
continue
subset.append(A[i]) # değilse aᵢ kesin içeride
t -= A[i]
return subset
def brute_subset_sum(A, T):
"""Bağımsız tanık (2ⁿ bitmask, DP'siz): herhangi alt küme T'ye toplanır mı?"""
n = len(A)
for mask in range(1 << n):
if sum(A[k] for k in range(n) if mask >> k & 1) == T:
return True
return False
def build_subset_example():
"""L18 §4 örneği: A = {2, 5, 7, 8, 9}; T = 21 → EVET (5+7+9);
T = 25 → HAYIR (kısa kanıt yok)."""
return [2, 5, 7, 8, 9], 21, 25
# ---------------------------------------------------------------------------
# _engine.py D28 (L19) §9 — Üç reduction (çalışır kod) + §6 doğrulayıcı
# ---------------------------------------------------------------------------
def reduce_unweighted_to_weighted(adj):
"""Reduction 1 (L19 §9): ağırlıksız SP → ağırlıklı SP. Her kenara w = 1
ver. Tanık: dijkstra(w=1) == bfs."""
return {(u, v): 1 for u in adj for v in adj[u]}
def reduce_integer_to_unweighted(adj, weight):
"""Reduction 2 (L19 §9): pozitif TAMSAYI ağırlık → ağırlıksız. Her
w-ağırlıklı kenarı w parçaya böl (w−1 ara düğüm). Boyut bedeli: Σw kenar
— sayılar büyükse pahalı (pseudopolinom bedel; D27 köprüsü)."""
adj2 = {v: [] for v in adj}
for u in adj:
for v in adj[u]:
w = weight[(u, v)]
prev = u
for k in range(1, w):
mid = (u, v, k)
adj2.setdefault(mid, [])
adj2[prev].append(mid)
prev = mid
adj2[prev].append(v)
return adj2
def dag_longest_path(adj, weight, s, topo):
"""Reduction 3 (L19 §9): en uzun yol → en kısa yol (negatifle). DAG'da
güvenli; genel çizgede en-uzun-BASİT-yol NP-hard. Negatifle → en kısa →
işaret çevir."""
negw = {e: -w for e, w in weight.items()}
d = dag_relaxation(adj, negw, s, topo)
return {v: (-d[v] if d[v] != INF else -INF) for v in adj}
def brute_dag_longest(adj, weight, s):
"""Bağımsız tanık (üstel, DP'siz): tüm yolları DFS ile gez, max."""
best = {v: -INF for v in adj}
best[s] = 0
def rec(u, total):
for v in adj[u]:
t2 = total + weight[(u, v)]
if t2 > best[v]:
best[v] = t2
rec(v, t2)
rec(s, 0)
return best
def verify_subset_certificate(A, T, cert):
"""NP Tanım-2 doğrulayıcısı (L19 §6): girdi (A, T) + certificate (alt
küme) al, POLİNOM zamanda kontrol et — (1) toplam T mi, (2) cert A'nın
çoklu-küme alt kümesi mi. O(|cert| + |A|). Döndürür: bool."""
if sum(cert) != T:
return False
pool = list(A)
for e in cert:
if e in pool:
pool.remove(e)
else:
return False
return True
```
## 1. Karmaşıklık: Alt Sınır Tarafı {#sec-1-karmasiklik-alt-sinir-tarafi}
Algoritmalar "iyi çözebiliriz" gösterir; karmaşıklık "**iyi çözemeyiz**" (alt sınır) kanıtlar. Eski alt sınırlar (sıralama $n \log n$) "$n$ vs $n \log n$" düzeyindeydi; bu ders **polinom vs üstel** düzeyinde. Polinom = iyi süre (her zaman hedefimiz); üstel = genelde kolay elde edilir (kaba kuvvet).
> *"cover an entire field, which is computational complexity."* — Demaine, 0:19
Perspektif tersine döner: dört DP dersi boyunca "ne kadar hızlı çözebiliriz?" diye sorduk; şimdi soru "**bu problem verimli çözülebilir mi, yoksa imkânsız mı?**"
## 2. P, EXP, R Hiyerarşisi {#sec-2-p-exp-r-hiyerarsisi}
- **P** = polinom-zamanda (girdi boyutu $n$'e polinom) çözülebilir problemler — "verimli".
- **EXP** = üstel-zamanda ($2^{n^c}$) çözülebilir. $P \subseteq EXP$ (ve kesin $P \neq EXP$).
- **R** = **sonlu** (recursive) zamanda çözülebilir. $P \subseteq EXP \subseteq R$.
> *"P... is the set of all problems solvable in polynomial time."* — Demaine, 1:50
Örnekler: **$n \times n$ satranç** EXP'de ama P'de değil (kanıtlı); **negatif çevrim tespiti** P'de (Bellman-Ford); **Tetris** (mükemmel-bilgi) EXP'de, P'de mi bilinmiyor. Çoğu problem **karar problemi**dir (yes/no çıktı).
@fig-class-hierarchy bu iç içe yapıyı tek bir zorluk ekseni üzerinde gösterir: $P \subseteq NP \subseteq EXP \subseteq R$ dört yarım-kapsül (ortak sol kenar, kademeli sağ kenar) hâlinde nest edilir; sınıf üyeliği bir **üst sınır** ("şu kadar zamanda çözülebilir"), NP-hard ise bir **alt sınır** ("bu noktanın sağında") olarak ayrışır. Motor tanığı NP'nin somut anlamını çalıştırır: subset sum'ın EVET girdisi ($A = \{2, 5, 7, 8, 9\}$, $T = 21$) için kısa-doğrulanabilir bir certificate vardır ($\{5, 7, 9\}$), HAYIR girdisi ($T = 25$) için yoktur — "NP = polinom-doğrulanabilir" rozetinin çalışan kanıtı.
```{python}
#| label: fig-class-hierarchy
#| fig-cap: "Hesaplama sınıfları hiyerarşisi (Demaine L19 §2 İMZA + Kontrol-4, 1:50): P ⊆ NP ⊆ EXP ⊆ R — soldan sağa zorluk artar, R dışı uncomputable. İç içe DÖRT yarım-kapsül (ortak sol kenar, kademeli sağ): P 'polinom-zamanda ÇÖZÜLEBİLİR' (örnek negatif çevrim tespiti Bellman-Ford O(V·E)), NP 'polinom-zamanda DOĞRULANABİLİR', EXP 'üstel-zamanda', R 'herhangi sonlu zamanda decidable'. NP sağ ucu amber şerit = NP-complete (Tetris/TSP/3-SAT rozetleri); EXP sağ ucu = EXP-complete (n×n satranç). NP-hard = NP-complete'ten SAĞA uzanan amber ok (alt sınır, kapsül dışına taşar). Eksenin SAĞ ÖTESİ kırmızı-soluk 'R DIŞI uncomputable' (halting problem). İki rozet: P ≠ EXP KESİN + P =? NP 1M$ AÇIK. Alt not: ÜST sınır = sınıf üyeliği · ALT sınır = X-hard. Motor tanığı (assert): build_subset_example == ([2,5,7,8,9],21,25); subset_sum_certificate(A,21)==[5,7,9] toplam 21; verify_subset_certificate(A,21,[5,7,9]) is True; subset_sum_certificate(A,25) is None (HAYIR için kısa kanıt yok); verify_subset_certificate(A,21,[2,8]) is False."
#| fig-width: 12.0
#| fig-height: 6.0
# fig-class-hierarchy (L19 §2 İMZA): sınıf hiyerarşisi. Motor tanığı: NP = poli-doğrulanabilir.
A_h, Tyes_h, Tno_h = build_subset_example()
assert A_h == [2, 5, 7, 8, 9] and Tyes_h == 21 and Tno_h == 25, (A_h, Tyes_h, Tno_h)
cert_h = subset_sum_certificate(A_h, Tyes_h)
assert cert_h == [5, 7, 9] and sum(cert_h) == Tyes_h, cert_h
assert verify_subset_certificate(A_h, Tyes_h, cert_h) is True
assert subset_sum_certificate(A_h, Tno_h) is None # HAYIR için cert yok
assert verify_subset_certificate(A_h, Tyes_h, [2, 8]) is False # uydurma cert
_BAND_FILL = {"P": "#cbd5e1", "NP": "#dbe1e9", "EXP": "#e6eaf0", "R": "#f1f4f8"}
_COL_UNCOMP = "#fbe3e0"
_COL_UNCOMP_EC = "#c0564c"
_COL_UNCOMP_TX = "#9b3b33"
def _badge(ax, cx, cy, text, *, fc, ec, tcol, fs=8.4, w=1.86, h=0.46,
weight="bold", style="normal"):
ax.add_patch(FancyBboxPatch(
(cx - w / 2, cy - h / 2), w, h,
boxstyle="round,pad=0.015,rounding_size=0.10",
fc=fc, ec=ec, linewidth=1.7, zorder=8))
ax.text(cx, cy, text, ha="center", va="center", fontsize=fs,
color=tcol, weight=weight, style=style, zorder=9)
fig, ax = plt.subplots(figsize=(12.0, 6.0))
fig.patch.set_facecolor(COL_WHITE)
x_left = 0.30
y_lo, y_hi = 0.95, 5.05
y_mid = (y_lo + y_hi) / 2
band_right = {"R": 9.55, "EXP": 7.55, "NP": 4.55, "P": 2.55}
band_order_out_to_in = ["R", "EXP", "NP", "P"]
band_pad = {"R": 0.0, "EXP": 0.46, "NP": 0.92, "P": 1.38}
for name in band_order_out_to_in:
pad = band_pad[name]
ax.add_patch(FancyBboxPatch(
(x_left, y_lo + pad), band_right[name] - x_left, (y_hi - pad) - (y_lo + pad),
boxstyle="round,pad=0.02,rounding_size=0.34",
fc=_BAND_FILL[name], ec=COL_SLATE_500,
linewidth=2.0, zorder=2 + band_order_out_to_in.index(name)))
label_x = x_left + 0.34
band_label_y = {"R": y_hi - 0.30, "EXP": y_hi - band_pad["EXP"] - 0.30,
"NP": y_hi - band_pad["NP"] - 0.30, "P": y_hi - band_pad["P"] - 0.30}
band_caption = {
"P": "polinom-zamanda ÇÖZÜLEBİLİR", "NP": "polinom-zamanda DOĞRULANABİLİR",
"EXP": "üstel-zamanda çözülebilir", "R": "herhangi sonlu zamanda (decidable)"}
for name in ["R", "EXP", "NP", "P"]:
ax.text(label_x, band_label_y[name], name, ha="left", va="center",
fontsize=13.5, color=COL_TEXT, weight="bold", zorder=10)
ax.text(label_x + 0.62, band_label_y[name], band_caption[name],
ha="left", va="center", fontsize=7.6, color=COL_SLATE_500,
style="italic", zorder=10)
npc_x = band_right["NP"]
npc_strip_w = 0.30
yy0 = y_lo + band_pad["NP"]
yy1 = y_hi - band_pad["NP"]
ax.add_patch(FancyBboxPatch(
(npc_x - npc_strip_w, yy0), npc_strip_w, yy1 - yy0,
boxstyle="round,pad=0.0,rounding_size=0.04",
fc=COL_AMBER_300, ec=COL_AMBER_700, linewidth=2.0, zorder=7))
ax.text(npc_x - npc_strip_w - 0.08, yy1 - 0.14, "NP-\ncomplete",
ha="right", va="top", fontsize=8.0, color=COL_AMBER_700, weight="bold", zorder=10)
npc_badge_x = npc_x + 1.00
_badge(ax, npc_badge_x, y_mid + 0.62, "Tetris",
fc=COL_AMBER_100, ec=COL_ACCENT, tcol=COL_AMBER_700, w=1.55)
_badge(ax, npc_badge_x, y_mid, "TSP",
fc=COL_AMBER_100, ec=COL_ACCENT, tcol=COL_AMBER_700, w=1.55)
_badge(ax, npc_badge_x, y_mid - 0.62, "3-SAT",
fc=COL_AMBER_100, ec=COL_ACCENT, tcol=COL_AMBER_700, w=1.55)
expc_x = band_right["EXP"]
yy0e = y_lo + band_pad["EXP"]
yy1e = y_hi - band_pad["EXP"]
ax.add_patch(FancyBboxPatch(
(expc_x - 0.30, yy0e), 0.30, yy1e - yy0e,
boxstyle="round,pad=0.0,rounding_size=0.04",
fc=COL_AMBER_600, ec=COL_AMBER_700, linewidth=2.0, zorder=6))
ax.text(expc_x - 0.30 - 0.08, yy1e - 0.14, "EXP-\ncomplete",
ha="right", va="top", fontsize=8.0, color=COL_AMBER_700, weight="bold", zorder=10)
_badge(ax, expc_x + 1.00, y_mid + 0.30, "n×n\nsatranç",
fc=COL_WHITE, ec=COL_AMBER_700, tcol=COL_AMBER_700, w=1.55, h=0.66, fs=8.0)
p_badge_y = y_lo + band_pad["P"] + 0.50
_badge(ax, x_left + 1.22, p_badge_y, "negatif çevrim\ntespiti",
fc=COL_WHITE, ec=COL_PRIMARY, tcol=COL_TEXT, w=1.95, h=0.62, fs=7.8)
ax.text(x_left + 1.22, p_badge_y - 0.52, "Bellman-Ford · O(V·E)",
ha="center", va="center", fontsize=6.8, color=COL_SLATE_500,
style="italic", zorder=10)
hard_y = y_lo + band_pad["NP"] + 0.05
ax.add_patch(FancyArrowPatch(
(npc_x, hard_y), (band_right["R"] + 0.55, hard_y),
arrowstyle="-|>", mutation_scale=18, color=COL_AMBER_700,
linewidth=2.6, zorder=9))
ax.text((npc_x + band_right["R"] + 0.55) / 2, hard_y - 0.26,
"NP-hard: \"bu noktanın SAĞINDA\" (en az NP-complete kadar zor)",
ha="center", va="center", fontsize=8.2, color=COL_AMBER_700,
weight="bold", zorder=10)
uncomp_x0 = band_right["R"] + 0.30
uncomp_x1 = 11.55
ax.add_patch(FancyBboxPatch(
(uncomp_x0, y_lo), uncomp_x1 - uncomp_x0, y_hi - y_lo,
boxstyle="round,pad=0.02,rounding_size=0.20",
fc=_COL_UNCOMP, ec=_COL_UNCOMP_EC, linewidth=2.0, linestyle="--", zorder=2))
ax.text((uncomp_x0 + uncomp_x1) / 2, y_hi - 0.34, "R DIŞI", ha="center",
va="center", fontsize=12.5, color=_COL_UNCOMP_TX, weight="bold", zorder=10)
ax.text((uncomp_x0 + uncomp_x1) / 2, y_hi - 0.74, "uncomputable", ha="center",
va="center", fontsize=8.4, color=_COL_UNCOMP_TX, style="italic", zorder=10)
_badge(ax, (uncomp_x0 + uncomp_x1) / 2, y_mid + 0.30, "halting\nproblem",
fc=COL_WHITE, ec=_COL_UNCOMP_EC, tcol=_COL_UNCOMP_TX, w=1.95, h=0.66, fs=8.2)
ax.text((uncomp_x0 + uncomp_x1) / 2, y_mid - 0.42, "hiçbir algoritma\nkarar veremez",
ha="center", va="center", fontsize=7.2, color=_COL_UNCOMP_TX,
style="italic", zorder=10)
_badge(ax, 3.85, y_hi + 0.55, "P ≠ EXP (KESİN)",
fc=COL_BG, ec=COL_PRIMARY, tcol=COL_PRIMARY, w=2.55, h=0.50, fs=9.5)
_badge(ax, 6.85, y_hi + 0.55, "P =? NP (1M$ AÇIK)",
fc=COL_AMBER_100, ec=COL_ACCENT, tcol=COL_AMBER_700, w=2.75, h=0.50, fs=9.5)
axis_y = 0.42
ax.add_patch(FancyArrowPatch(
(x_left - 0.10, axis_y), (uncomp_x1 + 0.05, axis_y),
arrowstyle="-|>", mutation_scale=20, color=COL_PRIMARY, linewidth=2.4, zorder=5))
ax.text(x_left + 0.05, axis_y - 0.30, "kolay", ha="left", va="center",
fontsize=9.5, color=COL_SLATE_500, weight="bold", zorder=6)
ax.text(uncomp_x1 - 0.05, axis_y - 0.30, "zor / imkânsız", ha="right",
va="center", fontsize=9.5, color=_COL_UNCOMP_TX, weight="bold", zorder=6)
ax.text((x_left + uncomp_x1) / 2, axis_y - 0.30, "ZORLUK →", ha="center",
va="center", fontsize=9.0, color=COL_PRIMARY, style="italic", zorder=6)
ax.text((x_left + uncomp_x1) / 2, -0.20,
"ÜST sınır = sınıf üyeliği (P/NP/EXP/R: \"şu kadar zamanda "
"ÇÖZÜLEBİLİR/DOĞRULANABİLİR\") · "
"ALT sınır = X-hard (\"en az X kadar zor\"; NP-hard NP'nin DIŞINA taşabilir)",
ha="center", va="center", fontsize=8.0, color=COL_SLATE_500, zorder=6)
fig.suptitle(
"Hesaplama sınıfları hiyerarşisi: P ⊆ NP ⊆ EXP ⊆ R — "
"soldan sağa zorluk artar, R dışı uncomputable",
color=COL_TEXT, fontsize=13.0, weight="bold", y=0.985)
ax.set_xlim(x_left - 0.55, uncomp_x1 + 0.45)
ax.set_ylim(-0.55, y_hi + 0.95)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
## 3. Halting Problem: Uncomputable {#sec-3-halting-problem-uncomputable}
$R$'nin de dışında problemler var. En ünlüsü **halting problem**: "verilen bir program durur mu (sonsuz döngü var mı)?"
> *"Given a computer program, does it ever halt?"* — Demaine, 10:49
Bu, mükemmel bir hata bulucu olurdu — ama **imkânsızdır**: tüm girdileri çözen bir algoritma yoktur. Böyle problemlere **uncomputable** ($R$ dışı) denir.
> *"We call such problems uncomputable."* — Demaine, 11:36
## 4. Çoğu Problem Çözülemez {#sec-4-cogu-problem-cozulemez}
Şaşırtıcı gerçek: çoğu karar problemi uncomputable. **Sayma argümanı**:
- **Program** = sonlu bit dizisi → bir doğal sayı. Doğal sayılar **sayılabilir (countable)**.
- **Karar problemi** = her girdi (sonsuz girdi) için yes/no → sonsuz bit dizisi → $[0, 1]$ aralığında bir **reel sayı**. Reel sayılar **sayılamaz (uncountable)**.
Reel sayılar, doğal sayılardan "çok daha fazladır" → problemlere yetecek kadar program **yoktur** → çoğu problem çözülemez. Şans eseri, **önemsediğimiz çoğu problem $R$'dedir** ($n \times n$ satranç bile — yalnız yavaş).
@fig-counting-argument bu argümanı iki panelde somutlaştırır: solda programlar kısa→uzun sonlu bit dizileri olarak doğal sayılara eşlenir (tam $8$-bit program sayısı $= 2^8 = 256$, sonlu); sağda tek bir karar problemi sonsuz bit dizisi → $[0, 1]$ reel sayı olur ve mini Cantor köşegen şeması (köşegeni ters çevir → listede olmayan problem) reel'in "kat kat fazla" olduğunu gösterir. Ortadaki köprü $\mathbb{N} \ll \mathbb{R}$ → "problemlere yetecek program yok" çıkarımını taşır.
```{python}
#| label: fig-counting-argument
#| fig-cap: "Sayma argümanı (Demaine L19 §4 İMZA, 1:32): programlar SAYILABİLİR, problemler SAYILAMAZ → çoğu problem ÇÖZÜLEMEZ (uncomputable). SOL panel 'PROGRAMLAR — sayılabilir': kısa→uzun sonlu bit dizileri (0,1,00,01,10,11) doğal sayılara (#1..#6) eşlenmiş; rozet 'her program = SONLU bit dizisi = bir doğal sayı (ℕ)'; tam 8-bit program sayısı 2⁸ = 256, uzunluk ≤ 8 program sayısı 2⁹−1 = 511 (SONLU). ORTA köprü: ℕ ≪ ℝ (sayılabilir ≪ sayılamaz) → amber kutu 'problemlere yetecek program YOK → çoğu problem UNCOMPUTABLE (Demaine 1:32)'. SAĞ panel 'KARAR PROBLEMLERİ — sayılamaz': tek problem = her girdi için evet/hayır = SONSUZ bit dizisi → 0.0110101… ∈ [0,1] reel; mini Cantor 4×4 köşegen tablosu + çevrilmiş köşegen P* 'her biti çevir → listede YOK'; rozet 'reel sayılar ≫ doğal sayılar (Cantor)'. Alt not: neyse ki önemsediğimiz çoğu problem R'dedir. Veri CANLI hesap (assert): prog_count_exact(8)==256; prog_count_upto(8)==511; diag_flip(Cantor) listedeki hiçbir satıra eşit değil + köşegen biti ters çevrilmiş."
#| fig-width: 12.0
#| fig-height: 5.8
# fig-counting-argument (L19 §4 İMZA): sayma argümanı. Veri CANLI hesap + assert.
def prog_count_exact(L):
return 2 ** L
def prog_count_upto(L):
return sum(2 ** i for i in range(L + 1))
def diag_flip(table):
return [1 - table[i][i] for i in range(len(table))]
def enumerate_programs(max_len):
out = []
for L in range(1, max_len + 1):
for v in range(2 ** L):
out.append(format(v, "0{}b".format(L)))
return out
_CANTOR = [[0, 1, 1, 0], [1, 1, 0, 1], [0, 0, 1, 1], [1, 0, 1, 0]]
assert prog_count_exact(8) == 256
assert prog_count_upto(8) == 511
_progs6 = enumerate_programs(2)[:6]
assert _progs6 == ["0", "1", "00", "01", "10", "11"], _progs6
_flip = diag_flip(_CANTOR)
for _r in range(len(_CANTOR)):
assert _flip != _CANTOR[_r], (_r, _flip)
for _i in range(len(_CANTOR)):
assert _flip[_i] == 1 - _CANTOR[_i][_i], (_i, _flip)
def _draw_left(ax):
progs = enumerate_programs(2)
show = progs[:6]
ax.text(2.55, 5.35, "PROGRAMLAR — sayılabilir", ha="center", va="center",
fontsize=13, color=COL_PRIMARY, weight="bold", zorder=7)
ax.text(2.55, 5.35 - 0.42, "kısa → uzun tüm SONLU bit dizileri", ha="center",
va="center", fontsize=9, color=COL_SLATE_500, style="italic", zorder=7)
row_y0, row_gap, nat_x, prog_x = 4.30, 0.66, 4.30, 0.95
for idx, bits in enumerate(show):
y = row_y0 - idx * row_gap
ax.add_patch(FancyBboxPatch(
(prog_x - 0.85, y - 0.23), 1.70, 0.46,
boxstyle="round,pad=0.02,rounding_size=0.08",
fc=COL_BG, ec=COL_PRIMARY, linewidth=1.7, zorder=3))
ax.text(prog_x, y, bits, ha="center", va="center", fontsize=11.5,
color=COL_TEXT, weight="bold", family="monospace", zorder=4)
ax.add_patch(FancyArrowPatch(
(prog_x + 0.92, y), (nat_x - 0.62, y), arrowstyle="-|>",
mutation_scale=12, color=COL_SLATE_400, linewidth=1.6, zorder=2))
ax.add_patch(Circle((nat_x, y), 0.30, facecolor=COL_AMBER_100,
edgecolor=COL_ACCENT, linewidth=2.0, zorder=4))
ax.text(nat_x, y, "#{}".format(idx + 1), ha="center", va="center",
fontsize=10, color=COL_AMBER_700, weight="bold", zorder=5)
y_dots = row_y0 - len(show) * row_gap + 0.04
ax.text(prog_x, y_dots, "⋮", ha="center", va="center", fontsize=14,
color=COL_SLATE_500, zorder=4)
ax.text(nat_x, y_dots, "⋮", ha="center", va="center", fontsize=14,
color=COL_SLATE_500, zorder=4)
ax.text(prog_x, row_y0 + 0.52, "bit dizisi", ha="center", va="center",
fontsize=8.5, color=COL_SLATE_500, style="italic", zorder=5)
ax.text(nat_x, row_y0 + 0.52, "doğal sayı", ha="center", va="center",
fontsize=8.5, color=COL_SLATE_500, style="italic", zorder=5)
ax.add_patch(FancyBboxPatch(
(-0.05, -0.40), 5.20, 0.62, boxstyle="round,pad=0.03,rounding_size=0.10",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.2, zorder=3))
ax.text(2.55, -0.09, "her program = SONLU bit dizisi = bir doğal sayı (ℕ)",
ha="center", va="center", fontsize=10, color=COL_AMBER_700,
weight="bold", zorder=5)
ax.text(2.55, -1.05, "tam 8-bit program sayısı: 2⁸ = {}".format(prog_count_exact(8)),
ha="center", va="center", fontsize=10, color=COL_TEXT, weight="bold", zorder=5)
ax.text(2.55, -1.50,
"uzunluk ≤ 8 program sayısı: 2⁰+…+2⁸ = 2⁹−1 = {} (SONLU)".format(prog_count_upto(8)),
ha="center", va="center", fontsize=8.5, color=COL_SLATE_500,
style="italic", zorder=5)
def _draw_bridge(fig):
axB = fig.add_axes([0.405, 0.10, 0.19, 0.80])
axB.set_xlim(0, 1)
axB.set_ylim(0, 1)
axB.axis("off")
axB.text(0.5, 0.74, "ℕ ≪ ℝ", ha="center", va="center", fontsize=20,
color=COL_PRIMARY, weight="bold", zorder=6)
axB.text(0.5, 0.635, "sayılabilir ≪ sayılamaz", ha="center", va="center",
fontsize=8, color=COL_SLATE_500, style="italic", zorder=6)
axB.add_patch(FancyArrowPatch(
(0.5, 0.585), (0.5, 0.46), arrowstyle="-|>", mutation_scale=15,
color=COL_ACCENT, linewidth=2.4, zorder=5))
axB.add_patch(FancyBboxPatch(
(0.02, 0.205), 0.96, 0.245, boxstyle="round,pad=0.02,rounding_size=0.06",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.6, zorder=4))
axB.text(0.5, 0.385, "problemlere yetecek", ha="center", va="center",
fontsize=9.5, color=COL_AMBER_700, weight="bold", zorder=6)
axB.text(0.5, 0.305, "program YOK", ha="center", va="center",
fontsize=11.5, color=COL_AMBER_700, weight="bold", zorder=6)
axB.text(0.5, 0.235, "→ çoğu problem", ha="center", va="center",
fontsize=9, color=COL_TEXT, weight="bold", zorder=6)
axB.text(0.5, 0.135, "UNCOMPUTABLE", ha="center", va="center",
fontsize=11, color=COL_PRIMARY, weight="bold", zorder=6)
axB.text(0.5, 0.075, "(Demaine 1:32)", ha="center", va="center",
fontsize=7.5, color=COL_SLATE_500, style="italic", zorder=6)
def _draw_right(ax, flipped):
ax.text(2.55, 5.35, "KARAR PROBLEMLERİ — sayılamaz", ha="center", va="center",
fontsize=13, color=COL_PRIMARY, weight="bold", zorder=7)
ax.text(2.55, 5.35 - 0.42,
"tek problem = her girdi için evet/hayır = SONSUZ bit dizisi",
ha="center", va="center", fontsize=8.5, color=COL_SLATE_500,
style="italic", zorder=7)
strip_y, strip_x0, cell = 4.30, 0.30, 0.42
sample = _CANTOR[0] + [1, 0, 1]
for i, b in enumerate(sample):
x = strip_x0 + i * cell
ax.add_patch(FancyBboxPatch(
(x, strip_y - cell * 0.45), cell * 0.92, cell * 0.9,
boxstyle="square,pad=0.0", fc=COL_BG, ec=COL_PRIMARY,
linewidth=1.3, zorder=3))
ax.text(x + cell * 0.46, strip_y, str(b), ha="center", va="center",
fontsize=9, color=COL_TEXT, weight="bold", family="monospace", zorder=4)
ax.text(strip_x0 + len(sample) * cell + 0.05, strip_y, "⋯", ha="left",
va="center", fontsize=12, color=COL_SLATE_500, zorder=4)
ax.text(2.55, strip_y + 0.55, "0.0110101… ∈ [0, 1] reel sayı", ha="center",
va="center", fontsize=9.5, color=COL_AMBER_700, weight="bold", zorder=5)
n = len(_CANTOR)
tbl_x0, tbl_y0, tc = 1.10, 2.95, 0.52
for r in range(n):
ax.text(tbl_x0 - 0.40, tbl_y0 - r * tc - tc * 0.5, "P{}".format(r + 1),
ha="right", va="center", fontsize=8.5, color=COL_SLATE_500,
weight="bold", zorder=5)
for c in range(n):
x = tbl_x0 + c * tc
y = tbl_y0 - (r + 1) * tc
on_diag = (r == c)
ax.add_patch(FancyBboxPatch(
(x, y), tc * 0.92, tc * 0.92, boxstyle="square,pad=0.0",
fc=COL_AMBER_100 if on_diag else COL_BG,
ec=COL_ACCENT if on_diag else COL_SLATE_400,
linewidth=2.4 if on_diag else 1.2, zorder=3))
ax.text(x + tc * 0.46, y + tc * 0.46, str(_CANTOR[r][c]),
ha="center", va="center", fontsize=10,
color=COL_AMBER_700 if on_diag else COL_TEXT,
weight="bold", family="monospace", zorder=4)
ax.text(tbl_x0 + n * tc + 0.25, tbl_y0 - tc * 0.5, "köşegen", ha="left",
va="center", fontsize=8.5, color=COL_AMBER_700, weight="bold", zorder=5)
ax.add_patch(FancyArrowPatch(
(tbl_x0 + n * tc + 0.20, tbl_y0 - tc * 0.5),
(tbl_x0 + (n - 1) * tc + tc * 0.5, tbl_y0 - tc * 1.5),
arrowstyle="-|>", mutation_scale=10, color=COL_AMBER_700,
linewidth=1.4, connectionstyle="arc3,rad=-0.3", zorder=4))
new_y = tbl_y0 - (n + 1) * tc - 0.18
ax.text(tbl_x0 - 0.40, new_y + tc * 0.46, "P*", ha="right", va="center",
fontsize=9, color=COL_ACCENT, weight="bold", zorder=5)
for c in range(n):
x = tbl_x0 + c * tc
ax.add_patch(FancyBboxPatch(
(x, new_y), tc * 0.92, tc * 0.92, boxstyle="square,pad=0.0",
fc=COL_WHITE, ec=COL_ACCENT, linewidth=2.0, zorder=3))
ax.text(x + tc * 0.46, new_y + tc * 0.46, str(flipped[c]),
ha="center", va="center", fontsize=10, color=COL_ACCENT,
weight="bold", family="monospace", zorder=4)
ax.text(tbl_x0 + n * tc + 0.25, new_y + tc * 0.46, "her biti çevir →\nlistede YOK",
ha="left", va="center", fontsize=8, color=COL_AMBER_700, weight="bold", zorder=5)
ax.add_patch(FancyBboxPatch(
(-0.05, -1.20), 5.20, 0.62, boxstyle="round,pad=0.03,rounding_size=0.10",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.2, zorder=3))
ax.text(2.55, -0.89, "reel sayılar ≫ doğal sayılar (Cantor: sayılamaz çokluk)",
ha="center", va="center", fontsize=10, color=COL_AMBER_700,
weight="bold", zorder=5)
fig, (axL, axR) = plt.subplots(1, 2, figsize=(12.0, 5.8))
fig.patch.set_facecolor(COL_WHITE)
_draw_left(axL)
axL.set_xlim(-0.7, 5.7)
axL.set_ylim(-1.9, 5.8)
axL.set_aspect("equal")
axL.axis("off")
_draw_right(axR, _flip)
axR.set_xlim(-0.7, 5.7)
axR.set_ylim(-1.9, 5.8)
axR.set_aspect("equal")
axR.axis("off")
fig.suptitle(
"Sayma argümanı: programlar SAYILABİLİR, problemler SAYILAMAZ → "
"çoğu problem ÇÖZÜLEMEZ (uncomputable)",
color=COL_TEXT, fontsize=12.5, weight="bold", y=0.985)
fig.text(0.5, 0.018,
"neyse ki önemsediğimiz çoğu problem hesaplanabilir R sınıfındadır "
"(çözülemez problemler genelde patolojiktir)",
ha="center", va="center", fontsize=8.5, color=COL_SLATE_500, style="italic")
plt.tight_layout(rect=(0, 0.04, 1, 0.95))
_draw_bridge(fig)
plt.show()
```
## 5. NP: Tanım 1 — Şanslı Algoritma {#sec-5-np-tanim-1-sansli-algoritma}
**NP** ($P \subseteq NP \subseteq EXP$), yalnız **karar problemleri** için. P gibi "polinom-zamanda çözülebilir" ama **şanslı algoritma** ile.
> *"a lucky algorithm, which can make guesses and always makes the right guess."* — Demaine, 22:46
Şanslı algoritma: tahmin yapabilir ve **bir "evet"e götüren yol varsa** hep doğru tahmin eder (non-deterministic polynomial time). DP'deki "tahmin et" sezgisinin gerçek hâli — ama DP tüm seçenekleri denerken, şanslı algoritma yalnız doğru tahminin maliyetini öder. **Asimetri:** "evet"i bulur, "hayır"ı garanti etmez.
## 6. NP: Tanım 2 — Doğrulayıcı {#sec-6-np-tanim-2-dogrulayici}
Eşdeğer tanım: NP = **polinom-zamanda doğrulanabilen (checkable)** karar problemleri.
> *"NP is a set of decision problems that can be checked in polynomial time."* — Demaine, 31:31
Bir **doğrulayıcı (verifier)** girdi + **certificate** (kanıt) alır, polinom-zamanda yes/no der. İki koşul: (1) her **evet** girdisi için, doğrulayıcıyı "evet" dedirten bir certificate **vardır**; (2) her **hayır** girdisi için, *hiçbir* certificate doğrulayıcıyı "evet" dedirtmez. Yani "evet"ler ispatlanabilir, "hayır"lar değil. Örnek: subset sum (alt kümeyi göster → topla, doğrula); Tetris (hamle dizisi = certificate, kuralları uygula).
@fig-np-two-defs NP'nin iki tanımını tek figürde, motor üzerinde birleştirir: üst panelde şanslı makine $A = \{2, 5, 7, 8, 9\}$, $T = 21$ için karar ağacında hep doğru tahmin eder ve $\{5, 7, 9\} \to 21$ EVET yaprağına ulaşır (amber yol); "tahminleri yazarsan certificate olur" köprüsü Tanım-2'ye bağlanır. Alt panelde doğrulayıcı, certificate $\{5, 7, 9\}$'u $O(|\text{cert}| + |A|)$'da kontrol eder ($5 + 7 + 9 = 21 \checkmark$), kötü certificate $\{5, 7, 8\}$'i ($= 20 \neq 21$) reddeder; asimetri rozeti $T = 25 \to$ certificate `None` ile "hayır kısa-kanıtlanamaz"ı gösterir.
```{python}
#| label: fig-np-two-defs
#| fig-cap: "NP'nin iki eşdeğer tanımı (Demaine L19 §5-6, 22:46 + 31:31): ŞANSLI tahmin ≡ hızlı DOĞRULAMA. ÜST panel 'Tanım 1 — ŞANSLI algoritma': karar ağacı kökte A={2,5,7,8,9}, T=21; her öğede koy/koyma tahmini; şanslı makine bir EVET-yolu VARSA hep doğru tahmin eder ve {5,7,9}→21 ✓ EVET yaprağına ulaşır (amber yol, diğer dallar soluk); köprü kutusu 'tahminleri YAZARSAN → certificate olur = Tanım 2'ye köprü (Demaine 22:46)'. ALT panel 'Tanım 2 — DOĞRULAYICI': akış (A,T)+cert {5,7,9} → VERIFIER O(|cert|+|A|) → '5+7+9 = 21 == 21 ✓ EVET'; kötü cert {5,7,8} → '5+7+8 = 20 ≠ 21 ✗ red'; iki koşul kutusu (1) her EVET için cert VAR (2) hiçbir HAYIR için cert YOK; ASİMETRİ rozeti 'EVET ispatlanabilir · HAYIR DEĞİL — T=25 → cert = None'. Veri MOTORDAN (assert): build_subset_example == ([2,5,7,8,9],21,25); subset_sum_certificate(A,21)==[5,7,9] toplam 21; verify_subset_certificate(A,21,[5,7,9]) is True; verify_subset_certificate(A,21,[5,7,8]) is False (toplam 20); subset_sum(A,25)[0] is False; subset_sum_certificate(A,25) is None."
#| fig-width: 11.5
#| fig-height: 6.5
# fig-np-two-defs (L19 §5-6): NP iki tanım. Veri MOTORDAN.
A_n, Tyes_n, Tno_n = build_subset_example()
assert A_n == [2, 5, 7, 8, 9] and Tyes_n == 21 and Tno_n == 25
cert_n = subset_sum_certificate(A_n, Tyes_n)
assert cert_n == [5, 7, 9] and sum(cert_n) == Tyes_n, cert_n
assert verify_subset_certificate(A_n, Tyes_n, cert_n) is True
bad_cert_n = [5, 7, 8]
assert verify_subset_certificate(A_n, Tyes_n, bad_cert_n) is False
assert sum(bad_cert_n) == 20
assert subset_sum(A_n, Tno_n)[0] is False
assert subset_sum_certificate(A_n, Tno_n) is None
fig, (ax_top, ax_bot) = plt.subplots(
2, 1, figsize=(11.5, 6.5), gridspec_kw={"height_ratios": [1.0, 0.92]})
fig.patch.set_facecolor(COL_WHITE)
# ===== ÜST PANEL — Tanım 1: ŞANSLI (nondeterministik) algoritma =====
ax = ax_top
ax.set_facecolor(COL_WHITE)
lucky = [(2, "koyma"), (5, "koy"), (7, "koy"), (8, "koyma"), (9, "koy")]
assert sum(e for e, dec in lucky if dec == "koy") == Tyes_n
x_root = 1.6
y_levels = [4.6, 3.7, 2.8, 1.9, 1.0, 0.1]
dx = 1.45
rx, ry = x_root, y_levels[0]
ax.add_patch(FancyBboxPatch(
(rx - 1.05, ry - 0.26), 2.10, 0.52,
boxstyle="round,pad=0.03,rounding_size=0.08",
fc=COL_BG, ec=COL_PRIMARY, linewidth=1.8, zorder=4))
ax.text(rx, ry, "A={2,5,7,8,9}, T=%d" % Tyes_n, ha="center", va="center",
fontsize=9.5, color=COL_TEXT, weight="bold", zorder=5)
px, py = rx, ry
for k, (elem, dec) in enumerate(lucky):
y_child = y_levels[k + 1]
lucky_left = (dec == "koyma")
lx = px - dx * (0.78 ** k)
rx2 = px + dx * (0.78 ** k)
lucky_x = lx if lucky_left else rx2
other_x = rx2 if lucky_left else lx
ax.plot([px, other_x], [py, y_child], color=COL_SLATE_400,
linewidth=1.2, alpha=0.7, zorder=2)
ax.add_patch(Circle((other_x, y_child), 0.09, facecolor=COL_WHITE,
edgecolor=COL_SLATE_400, linewidth=1.2, zorder=3))
ax.text(other_x, y_child - 0.24, "…", ha="center", va="center",
fontsize=11, color=COL_SLATE_400, zorder=3)
other_dec = "koy" if dec == "koyma" else "koyma"
ax.text((px + other_x) / 2 + (0.18 if other_x > px else -0.18),
(py + y_child) / 2, "%d:%s" % (elem, other_dec), ha="center",
va="center", fontsize=7.0, color=COL_SLATE_400, zorder=3)
ax.add_patch(FancyArrowPatch(
(px, py - 0.10), (lucky_x, y_child + 0.16), arrowstyle="-|>",
mutation_scale=12, color=COL_ACCENT, linewidth=2.4, zorder=4,
shrinkA=2, shrinkB=2))
ax.text((px + lucky_x) / 2 + (0.20 if lucky_x > px else -0.20),
(py + y_child) / 2 + 0.06, "%d:%s" % (elem, dec), ha="center",
va="center", fontsize=8.0, color=COL_AMBER_700, weight="bold", zorder=5)
ax.add_patch(Circle((lucky_x, y_child), 0.14, facecolor=COL_AMBER_100,
edgecolor=COL_ACCENT, linewidth=2.2, zorder=5))
px, py = lucky_x, y_child
ax.add_patch(FancyBboxPatch(
(px - 1.15, py - 0.42), 2.30, 0.52, boxstyle="round,pad=0.03,rounding_size=0.08",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=2.2, zorder=6))
ax.text(px, py - 0.16, "{5,7,9} → 21 ✓ EVET", ha="center", va="center",
fontsize=9.5, color=COL_AMBER_700, weight="bold", zorder=7)
bx = 4.55
ax.add_patch(FancyBboxPatch(
(bx, 0.55), 4.30, 3.55, boxstyle="round,pad=0.05,rounding_size=0.12",
fc=COL_BG, ec=COL_PRIMARY, linewidth=1.6, zorder=3))
ax.text(bx + 0.25, 3.78, "ŞANSLI makine (NP Tanım 1)", ha="left", va="center",
fontsize=10.5, color=COL_TEXT, weight="bold", zorder=5)
for i, line in enumerate([
"bir EVET-yolu VARSA", "makine HEP doğru tahmin eder",
"(Demaine 22:46)", "", "tahminleri YAZARSAN",
"→ certificate olur", "= Tanım 2'ye köprü"]):
col = COL_SLATE_500 if i < 3 else COL_AMBER_700
wt = "normal" if i < 3 else "bold"
st = "italic" if i == 2 else "normal"
ax.text(bx + 0.25, 3.30 - i * 0.40, line, ha="left", va="center",
fontsize=9.2, color=col, weight=wt, style=st, zorder=5)
ax.set_title("Tanım 1 — ŞANSLI algoritma: doğru tahmin dizisi = certificate",
color=COL_TEXT, fontsize=12, weight="bold", loc="left")
ax.set_xlim(-1.6, 9.1)
ax.set_ylim(-0.55, 5.05)
ax.axis("off")
# ===== ALT PANEL — Tanım 2: DOĞRULAYICI (verifier) =====
ax = ax_bot
ax.set_facecolor(COL_WHITE)
def _box(x, y, w, h, text, fc, ec, lw=1.8, fs=9.5, tc=None, bold=True):
ax.add_patch(FancyBboxPatch(
(x - w / 2, y - h / 2), w, h, boxstyle="round,pad=0.03,rounding_size=0.08",
fc=fc, ec=ec, linewidth=lw, zorder=4))
ax.text(x, y, text, ha="center", va="center", fontsize=fs,
color=tc or COL_TEXT, weight="bold" if bold else "normal", zorder=5)
def _arrow(x0, y0, x1, y1, color=COL_PRIMARY, lw=2.0):
ax.add_patch(FancyArrowPatch(
(x0, y0), (x1, y1), arrowstyle="-|>", mutation_scale=14,
color=color, linewidth=lw, zorder=3, shrinkA=3, shrinkB=3))
y_g = 3.05
_box(0.95, y_g, 1.85, 0.62, "girdi (A, T=%d)" % Tyes_n, COL_BG, COL_PRIMARY)
_box(0.95, y_g - 0.92, 1.85, 0.56, "cert {5,7,9}", COL_AMBER_100, COL_ACCENT, tc=COL_AMBER_700)
_arrow(1.88, y_g, 3.25, y_g - 0.30)
_arrow(1.88, y_g - 0.92, 3.25, y_g - 0.62)
_box(4.05, y_g - 0.46, 1.55, 1.05, "VERIFIER", COL_BG, COL_PRIMARY, lw=2.2)
ax.text(4.05, y_g - 1.18, "O(|cert|+|A|)", ha="center", va="center",
fontsize=7.5, color=COL_SLATE_500, style="italic", zorder=5)
_arrow(4.83, y_g - 0.46, 6.05, y_g - 0.30, color=COL_ACCENT, lw=2.4)
_box(7.30, y_g - 0.30, 2.55, 0.66, "5+7+9 = %d == %d ✓ EVET" % (sum(cert_n), Tyes_n),
COL_AMBER_100, COL_ACCENT, tc=COL_AMBER_700, fs=9.0)
y_b = 0.55
_box(0.95, y_b, 1.85, 0.56, "kötü cert {5,7,8}", COL_WHITE, COL_SLATE_400, tc=COL_SLATE_500)
_arrow(1.88, y_b, 3.25, y_g - 0.78, color=COL_SLATE_400, lw=1.6)
_arrow(4.83, y_g - 0.78, 6.05, y_b + 0.30, color=COL_SLATE_500, lw=1.8)
_box(7.30, y_b + 0.20, 2.55, 0.66, "5+7+8 = %d ≠ %d ✗ red" % (sum(bad_cert_n), Tyes_n),
COL_WHITE, COL_SLATE_400, tc=COL_SLATE_500, fs=9.0)
cx = 9.10
ax.add_patch(FancyBboxPatch(
(cx - 0.05, 1.05), 3.10, 1.95, boxstyle="round,pad=0.05,rounding_size=0.10",
fc=COL_BG, ec=COL_PRIMARY, linewidth=1.5, zorder=3))
ax.text(cx + 0.18, 2.78, "doğrulayıcının İKİ koşulu:", ha="left", va="center",
fontsize=8.8, color=COL_TEXT, weight="bold", zorder=5)
ax.text(cx + 0.18, 2.30, "(1) her EVET için\n cert VAR", ha="left", va="center",
fontsize=8.5, color=COL_AMBER_700, weight="bold", zorder=5)
ax.text(cx + 0.18, 1.55, "(2) hiçbir HAYIR için\n cert YOK", ha="left", va="center",
fontsize=8.5, color=COL_SLATE_500, weight="bold", zorder=5)
ax.add_patch(FancyBboxPatch(
(0.05, -1.10), 12.15, 0.78, boxstyle="round,pad=0.04,rounding_size=0.10",
fc=COL_AMBER_100, ec=COL_AMBER_600, linewidth=1.8, zorder=3))
ax.text(6.1, -0.71,
"ASİMETRİ: EVET ispatlanabilir (kısa cert) · "
"HAYIR DEĞİL — T=%d → cert = None (kısa kanıt YOK)" % Tno_n,
ha="center", va="center", fontsize=9.5, color=COL_AMBER_700,
weight="bold", zorder=5)
ax.set_title("Tanım 2 — DOĞRULAYICI: certificate'i polinom zamanda kontrol et",
color=COL_TEXT, fontsize=12, weight="bold", loc="left")
ax.set_xlim(-0.3, 12.4)
ax.set_ylim(-1.35, 3.65)
ax.axis("off")
fig.suptitle(
"NP'nin iki eşdeğer tanımı: ŞANSLI tahmin ≡ hızlı DOĞRULAMA",
color=COL_TEXT, fontsize=13.5, weight="bold", y=0.995)
plt.tight_layout(rect=(0, 0, 1, 0.97))
plt.show()
```
## 7. P ≠ NP Konjektürü {#sec-7-p-np-konjekturu}
$P \subseteq NP$ biliniyor; **$P = NP$ mi?** bilinmiyor (1 milyon dolarlık açık problem). Çoğunluk **$P \neq NP$** sanır.
> *"you cannot engineer luck."* — Demaine, 39:17
Sezgi: NP = şansla çözülebilir, P = şansız çözülebilir; $P = NP$ olsaydı "şans hiçbir şey kazandırmazdı" — ki tuhaf. Eşdeğer ifade:
> *"it's harder to come up with proofs than it is to check them."* — Demaine, 39:56
(İspat bulmak, doğrulamaktan zor.)
## 8. NP-hard ve NP-complete {#sec-8-np-hard-ve-np-complete}
- **NP-hard:** NP'deki *tüm* problemler kadar zor (alt sınır). NP'deki her problem buna **indirgenir**.
- **NP-complete:** NP **ve** NP-hard (NP'nin en zoru).
> *"NP-complete... the problems that are in NP and they are NP-hard."* — Demaine, 43:11
$P \neq NP$ ise, NP-tam problemler **P'de değildir** (polinom-zamanda çözülemez). Tetris NP-tamdır → $P \neq NP$ varsayımıyla, bir Tetris dizisini hayatta kalıp kalamayacağını polinom-zamanda hesaplayamazsın.
## 9. Reduction: İndirgeme ile Zorluk Kanıtı {#sec-9-reduction-indirgeme-ile-zorluk-kaniti}
**Reduction** (indirgeme): A'yı B'ye çevir — A girdisini B girdisine, B çözümünü A çözümüne. Algoritma için: çözmek istediğini bildiğine indirge. **Zorluk için: bilinen-zor problemi hedefe indirge.**
> *"Reductions are the easy way to use algorithms."* — Demaine, 44:38
Anlamı: $A \le B$ reduction'ı varsa, "A en az B kadar kolay" = "**B en az A kadar zor**". Gördüğümüz indirgemeler: ağırlıksız SP → ağırlıklı SP (ağırlık$=1$); tamsayı-ağırlık → ağırlıksız (kenar böl); en uzun yol → en kısa yol (negatifle). NP-hardness kanıtı: bilinen NP-tam bir problemi (örn. **3-partition**) hedefe indirge. 3-partition → jigsaw puzzle (NP-hard); 3-partition → Tetris (NP-hard).
@fig-reduction-direction reduction'ın **yönünü** — sınavların klasiği — iki panelde ayırır. Üst panel algoritma için reduction'ı ($A \le B$: bildiğine indirge) üç çalışır motor-tanığıyla gösterir: **R1** ağırlıksız → ağırlıklı SP ($w = 1$; `dijkstra` $=$ `bfs`, $\delta(s \to d) = 2$, $60$ rastgele çizgede aynı), **R2** tamsayı-ağırlık → ağırlıksız (kenar böl; $\delta(t) = 5$), **R3** en uzun → en kısa yol (negatifle; yalnız DAG güvenli, $e \to h = 11$, `brute` ile aynı). Alt panel zorluk için reduction'ı verir: bilinen-zor **3-partition** $\to$ **Tetris** (gadget), büyük amber yön oku "$A \le B \Rightarrow B$ en az $A$ kadar zor"; ters yön kırmızı çarpıyla yasaklanır ("hedefi kolay-bilinene indirgemek hiçbir şey kanıtlamaz").
```{python}
#| label: fig-reduction-direction
#| fig-cap: "Reduction YÖNÜ — sınavların klasiği (Demaine L19 §9 İMZA, 44:38). ÜST panel 'ALGORİTMA için reduction (A ≤ B: bildiğine indirge)': üç çalışır motor-tanığı — R1 ağırlıksız SP → ağırlıklı SP (w=1; dijkstra=bfs, δ(s→d)=2), R2 tamsayı-ağırlık SP → ağırlıksız SP (kenarı w parçaya böl; bfs(bölünmüş)=5, 3+2), R3 en UZUN yol → en KISA yol (negatifle −w; dag_longest=brute, e→h=11, yalnız DAG güvenli ✓); çöz B'yi kara kutu → cevabı A'ya geri çevir, amber kutu = «bildiğim» problem. ALT panel 'ZORLUK için reduction (bilinen-ZOR'u hedefe indirge)': 3-PARTITION (NP-zor BİLİNEN) → gadget → TETRIS (hedef); büyük amber yön oku 'A ≤ B ⟹ B EN AZ A kadar ZOR'; ters-yön kırmızı çarpılı ok 'hedefi kolay-bilinene indirgemek HİÇBİR ŞEY kanıtlamaz'; zincir 'Tetris polinom çözülseydi → 3-partition da çözülürdü → P = NP (Demaine 44:38)'. Veri MOTORDAN (assert): R1 dijkstra(w=1)==bfs, δ(s→d)=2; R2 reduce_integer_to_unweighted + bfs == dijkstra, δ(t)=5; R3 dag_longest_path==brute_dag_longest, e→h=11; subset cert [5,7,9] toplam 21 (NP-tam çıpa)."
#| fig-width: 12.0
#| fig-height: 6.2
# fig-reduction-direction (L19 §9 İMZA): reduction yönü. Veri MOTORDAN.
COL_RED_R = "#dc2626"
# R1: ağırlıksız SP → ağırlıklı SP (w=1)
adj_r1 = {"s": ["a", "b"], "a": ["c"], "b": ["c", "d"], "c": ["d"], "d": []}
bfs_delta, _ = bfs(adj_r1, "s")
w_r1 = reduce_unweighted_to_weighted(adj_r1)
dij_r1 = dijkstra(adj_r1, w_r1, "s")
assert all(dij_r1[v] == bfs_delta[v] for v in bfs_delta), "R1 dijkstra(w=1) != bfs"
R1_VAL = bfs_delta["d"]
assert R1_VAL == 2 and dij_r1["d"] == 2
# R2: tamsayı-ağırlık → ağırlıksız (kenar böl)
adj_r2 = {"s": ["a"], "a": ["t"], "t": []}
w_r2 = {("s", "a"): 3, ("a", "t"): 2}
adj_r2_split = reduce_integer_to_unweighted(adj_r2, w_r2)
bfs_split, _ = bfs(adj_r2_split, "s")
dij_r2 = dijkstra(adj_r2, w_r2, "s")
assert bfs_split["t"] == dij_r2["t"], "R2 bfs(split) != dijkstra"
R2_VAL = bfs_split["t"]
assert R2_VAL == 5
# R3: en uzun yol → en kısa yol (negatifle; yalnız DAG)
adj_r3, w_r3, topo_r3 = build_weighted_dag_example()
lp = dag_longest_path(adj_r3, w_r3, "e", topo_r3)
bp = brute_dag_longest(adj_r3, w_r3, "e")
assert all(lp[v] == bp[v] for v in lp), "R3 dag_longest != brute"
R3_VAL = lp["h"]
assert R3_VAL == 11 and bp["h"] == 11
# Alt panel köprüsü: subset sum certificate (D27, NP-tam çıpa)
A_ss, T_ss, _ = build_subset_example()
cert_ss = subset_sum_certificate(A_ss, T_ss)
assert verify_subset_certificate(A_ss, T_ss, cert_ss) and sum(cert_ss) == T_ss
def reduction_box(ax, x, y, w, h, text, fc, ec, lw=1.8, fontsize=10.5,
text_color=None, weight="bold"):
ax.add_patch(FancyBboxPatch(
(x - w / 2, y - h / 2), w, h, boxstyle="round,pad=0.02,rounding_size=0.06",
fc=fc, ec=ec, linewidth=lw, zorder=3))
ax.text(x, y, text, ha="center", va="center", fontsize=fontsize,
color=text_color or COL_TEXT, weight=weight, zorder=5)
def reduction_arrow(ax, x0, x1, y, label, color=COL_ACCENT, lw=2.6,
fontsize=8.5, label_color=None):
ax.add_patch(FancyArrowPatch(
(x0, y), (x1, y), arrowstyle="-|>", mutation_scale=18,
color=color, linewidth=lw, zorder=4))
ax.text((x0 + x1) / 2, y + 0.30, label, ha="center", va="center",
fontsize=fontsize, color=label_color or COL_AMBER_700,
weight="bold", zorder=5, style="italic")
fig, (ax_top, ax_bot) = plt.subplots(2, 1, figsize=(12, 6.2))
# ÜST PANEL — ALGORİTMA için reduction
bw, bh = 2.55, 0.78
xA, xB = 1.7, 8.3
y_rows = [2.55, 1.45, 0.35]
rows = [
("ağırlıksız SP", "w = 1", "ağırlıklı SP",
"R1: dijkstra = bfs, δ(s→d) = %d" % R1_VAL, COL_BG, COL_AMBER_100, True),
("tamsayı-ağırlık SP", "kenarı w parçaya böl", "ağırlıksız SP",
"R2: bfs(bölünmüş) = %d (3+2)" % R2_VAL, COL_BG, COL_AMBER_100, True),
("en UZUN yol", "negatifle (−w)", "en KISA yol",
"R3: dag_longest = brute, e→h = %d" % R3_VAL, COL_BG, COL_AMBER_100, False),
]
ax_top.text(5.0, 3.52, "ALGORİTMA için reduction (A ≤ B: bildiğine indirge)",
ha="center", va="center", fontsize=12.5, color=COL_PRIMARY, weight="bold")
for (a_lbl, t_lbl, b_lbl, witness, a_fc, b_fc, safe), yr in zip(rows, y_rows):
reduction_box(ax_top, xA, yr, bw, bh, a_lbl, a_fc, COL_PRIMARY)
reduction_arrow(ax_top, xA + bw / 2 + 0.15, xB - bw / 2 - 0.15, yr, t_lbl)
reduction_box(ax_top, xB, yr, bw, bh, b_lbl, b_fc, COL_ACCENT, lw=2.2)
if not safe:
ax_top.text(xB + bw / 2 + 0.35, yr + 0.20, "yalnız DAG", ha="left",
va="center", fontsize=7.8, color=COL_AMBER_700, weight="bold")
ax_top.text(xB + bw / 2 + 0.35, yr - 0.10, "güvenli ✓", ha="left",
va="center", fontsize=7.8, color=COL_AMBER_700, weight="bold")
ax_top.text(xA, yr - bh / 2 - 0.20, witness, ha="center", va="center",
fontsize=7.6, color=COL_SLATE_500, zorder=5)
ax_top.text(5.0, -0.42,
"çöz B'yi (kara kutu) → cevabı A'ya geri çevir · amber kutu = «bildiğim» problem",
ha="center", va="center", fontsize=8.6, color=COL_SLATE_500, style="italic")
ax_top.set_xlim(-0.6, 11.6)
ax_top.set_ylim(-0.85, 3.85)
ax_top.axis("off")
# ALT PANEL — ZORLUK için reduction
ax_bot.text(5.0, 3.45, "ZORLUK için reduction (bilinen-ZOR'u hedefe indirge)",
ha="center", va="center", fontsize=12.5, color=COL_PRIMARY, weight="bold")
yH = 2.25
xHard, xTarget = 1.9, 8.1
hbw, hbh = 2.7, 0.95
reduction_box(ax_bot, xHard, yH, hbw, hbh, "3-PARTITION\n(NP-zor, BİLİNEN)",
COL_AMBER_300, COL_AMBER_700, lw=2.2, fontsize=10.5, text_color=COL_TEXT)
reduction_box(ax_bot, xTarget, yH, hbw, hbh, "TETRIS\n(hedef problem)",
COL_BG, COL_PRIMARY, lw=2.0, fontsize=10.5)
ax_bot.add_patch(FancyArrowPatch(
(xHard + hbw / 2 + 0.15, yH), (xTarget - hbw / 2 - 0.15, yH),
arrowstyle="-|>", mutation_scale=26, color=COL_ACCENT, linewidth=3.4, zorder=4))
ax_bot.text((xHard + xTarget) / 2, yH + 0.42, "gadget", ha="center", va="center",
fontsize=9, color=COL_AMBER_700, weight="bold", style="italic")
ax_bot.text((xHard + xTarget) / 2, yH - 0.45, "A ≤ B ⟹ B EN AZ A kadar ZOR",
ha="center", va="center", fontsize=10.5, color=COL_AMBER_700, weight="bold")
y_trap = 0.78
ax_bot.add_patch(FancyArrowPatch(
(xTarget - hbw / 2 - 0.15, y_trap), (xHard + hbw / 2 + 0.15, y_trap),
arrowstyle="-|>", mutation_scale=20, color=COL_RED_R, linewidth=2.2,
linestyle=(0, (4, 3)), zorder=4, alpha=0.85))
xc = (xHard + xTarget) / 2
ax_bot.plot([xc - 0.22, xc + 0.22], [y_trap - 0.22, y_trap + 0.22],
color=COL_RED_R, linewidth=3.2, zorder=6)
ax_bot.plot([xc - 0.22, xc + 0.22], [y_trap + 0.22, y_trap - 0.22],
color=COL_RED_R, linewidth=3.2, zorder=6)
ax_bot.text(xc, y_trap - 0.50,
"hedefi kolay-bilinene indirgemek HİÇBİR ŞEY kanıtlamaz",
ha="center", va="center", fontsize=8.8, color=COL_RED_R, weight="bold")
ax_bot.text(5.0, -0.30,
"Tetris polinom çözülseydi → 3-partition da çözülürdü → P = NP",
ha="center", va="center", fontsize=9.5, color=COL_TEXT, weight="bold")
ax_bot.text(5.0, -0.72, "(Demaine 44:38)", ha="center", va="center",
fontsize=7.8, color=COL_SLATE_500, style="italic")
ax_bot.set_xlim(-0.6, 11.6)
ax_bot.set_ylim(-1.05, 3.8)
ax_bot.axis("off")
fig.tight_layout(pad=0.8)
plt.show()
```
Bu indirgemelerden ikincisi (**R2:** tamsayı-ağırlık → ağırlıksız) tek başına da öğreticidir: çünkü "ücretsiz" değildir. @fig-edge-split bu kenar-bölme reduction'ını motor üzerinde açar: solda orijinal ağırlıklı çizge ($a, b, c, d$; Dijkstra $\delta$: $a{:}0, b{:}3, c{:}1, d{:}5$), sağda her $w$-ağırlıklı kenar $w$ parçaya bölünmüş ağırlıksız çizge — BFS seviyeleri orijinal düğümlerde **birebir aynı** değerleri verir. Ama bedel: yeni düğüm sayısı $= \Sigma w = 11$; ağırlıklar büyürse çizge **patlar** — bu, subset sum'ın $T$ büyüdükçe patlaması (Ders 27, pseudopolinom) ile aynı köprüdür: girdi *bit sayısında* üstel.
```{python}
#| label: fig-edge-split
#| fig-cap: "R2 redüksiyonu (Demaine L19 §9, R2): tamsayı-ağırlık → ağırlıksız · bfs(bölünmüş) == dijkstra(orijinal). SOL panel 'Orijinal: AĞIRLIKLI çizge · Dijkstra δ rozetleri': 4 düğüm a,b,c,d kenar ağırlıkları (a→b:3, a→c:1, b→d:2, c→d:5); δ rozetleri motordan a:0, b:3, c:1, d:5; δ(a,d)=5 (a→b→d: 3+2=5 < a→c→d: 1+5=6); kaynak s=a. SAĞ panel 'Kenar-bölünmüş: AĞIRLIKSIZ çizge · BFS seviye rozetleri (AYNI)': her w-kenar w parçaya bölünür (a→b 3 parça/2 ara, a→c tek/0 ara, b→d 2 parça/1 ara, c→d 5 parça/4 ara, gri ara düğümler); BFS seviye rozetleri orijinal düğümlerde AYNI (amber) çünkü ağırlıksız kenar = 1 adım, w parça = w adım. Alt not: bedel Σw = 11 yeni düğüm — sayılar büyükse çizge PATLAR (pseudopolinom bedel · Ders 27 köprüsü). Veri MOTORDAN (assert): reduce_integer_to_unweighted + bfs orijinal düğümlerde == dijkstra (a:0,b:3,c:1,d:5); ara düğüm sayısı = Σw−|E| = 11−4 = 7; her kenarın parça sayısı = ağırlığı."
#| fig-width: 11.5
#| fig-height: 5.5
# fig-edge-split (L19 §9, R2): kenar-bölme reduction. Veri MOTORDAN.
ADJ_e = {"a": ["b", "c"], "b": ["d"], "c": ["d"], "d": []}
W_e = {("a", "b"): 3, ("a", "c"): 1, ("b", "d"): 2, ("c", "d"): 5}
SRC_e = "a"
_POS_e = {"a": (0.0, 0.0), "b": (1.0, 0.85), "c": (1.0, -0.85), "d": (2.0, 0.0)}
_R_e = 0.22
adj2_e = reduce_integer_to_unweighted(ADJ_e, W_e)
delta_e, _ = bfs(adj2_e, SRC_e)
d_e = dijkstra(ADJ_e, W_e, SRC_e)
assert d_e == {"a": 0, "b": 3, "c": 1, "d": 5}, d_e
for v in "abcd":
assert delta_e[v] == d_e[v], (v, delta_e[v], d_e[v])
inter_e = [k for k in adj2_e if isinstance(k, tuple)]
sigma_w_e = sum(W_e.values())
assert len(inter_e) == sigma_w_e - len(W_e) == 7, (len(inter_e), sigma_w_e)
per_edge_mids = {e: W_e[e] - 1 for e in W_e}
assert per_edge_mids == {("a", "b"): 2, ("a", "c"): 0, ("b", "d"): 1, ("c", "d"): 4}
def _draw_node_e(ax, x, y, label, badge, *, r=_R_e, fc=COL_BG, ec=COL_PRIMARY,
tcol=COL_TEXT, lw=2.2, fs=14):
ax.add_patch(Circle((x, y), r, facecolor=fc, edgecolor=ec, linewidth=lw, zorder=8))
ax.text(x, y, label, ha="center", va="center", fontsize=fs, color=tcol,
weight="bold", zorder=9)
if badge is not None:
bx, by = x + r * 0.95, y + r * 0.95
ax.add_patch(Circle((bx, by), r * 0.62, facecolor=COL_AMBER_100,
edgecolor=COL_AMBER_700, linewidth=2.0, zorder=10))
ax.text(bx, by, str(badge), ha="center", va="center", fontsize=10.5,
color=COL_AMBER_700, weight="bold", zorder=11)
def _draw_arrow_e(ax, p0, p1, *, col=COL_PRIMARY, lw=2.0, sa=0.0, sb=0.0, ms=14, zorder=2):
ax.add_patch(FancyArrowPatch(
p0, p1, arrowstyle="-|>", mutation_scale=ms, color=col, linewidth=lw,
shrinkA=sa, shrinkB=sb, zorder=zorder))
fig, (axL, axR) = plt.subplots(1, 2, figsize=(11.5, 5.5))
fig.patch.set_facecolor(COL_WHITE)
# SOL — orijinal ağırlıklı + Dijkstra
for u in ADJ_e:
for v in ADJ_e[u]:
x0, y0 = _POS_e[u]
x1, y1 = _POS_e[v]
_draw_arrow_e(axL, (x0, y0), (x1, y1), col=COL_PRIMARY, lw=2.2,
sa=_R_e * 1.9 * 28, sb=_R_e * 1.9 * 28, ms=15, zorder=2)
mx, my = (x0 + x1) * 0.5, (y0 + y1) * 0.5
ddx, ddy = x1 - x0, y1 - y0
nrm = (ddx * ddx + ddy * ddy) ** 0.5 or 1.0
pxn, pyn = -ddy / nrm, ddx / nrm
bx, by = mx + pxn * 0.18, my + pyn * 0.18
axL.add_patch(Circle((bx, by), 0.16, facecolor=COL_BG,
edgecolor=COL_SLATE_500, linewidth=1.4, zorder=6))
axL.text(bx, by, str(W_e[(u, v)]), ha="center", va="center", fontsize=10.5,
color=COL_SLATE_500, weight="bold", zorder=7)
for node in _POS_e:
x, y = _POS_e[node]
_draw_node_e(axL, x, y, node, d_e[node],
fc=(COL_AMBER_100 if node == SRC_e else COL_BG),
ec=(COL_ACCENT if node == SRC_e else COL_PRIMARY))
axL.text(_POS_e[SRC_e][0], _POS_e[SRC_e][1] - _R_e - 0.30, "kaynak s = a",
ha="center", va="center", fontsize=9, color=COL_AMBER_700, weight="bold", zorder=9)
axL.set_title("Orijinal: AĞIRLIKLI çizge · Dijkstra δ rozetleri",
color=COL_TEXT, fontsize=12, weight="bold")
axL.text(1.0, -1.55,
"kenar ağırlığı = adım maliyeti · δ(a,d)=5 (a→b→d: 3+2=5 < a→c→d: 1+5=6)",
ha="center", va="center", fontsize=8.2, color=COL_SLATE_500, style="italic", zorder=9)
axL.set_xlim(-0.7, 2.7)
axL.set_ylim(-1.85, 1.55)
axL.set_aspect("equal")
axL.axis("off")
# SAĞ — kenar-bölünmüş ağırlıksız + BFS
big_pos = {n: (px, py) for n, (px, py) in _POS_e.items()}
def _node_xy(node):
if isinstance(node, tuple):
u, v, k = node
w = W_e[(u, v)]
x0, y0 = big_pos[u]
x1, y1 = big_pos[v]
t = k / float(w)
return (x0 + (x1 - x0) * t, y0 + (y1 - y0) * t)
return big_pos[node]
for u in adj2_e:
ux, uy = _node_xy(u)
for v in adj2_e[u]:
vx, vy = _node_xy(v)
sa = _R_e * 1.9 * 28 if not isinstance(u, tuple) else 5 * 28
sb = _R_e * 1.9 * 28 if not isinstance(v, tuple) else 5 * 28
_draw_arrow_e(axR, (ux, uy), (vx, vy), col=COL_SLATE_400, lw=1.6,
sa=sa, sb=sb, ms=11, zorder=2)
for mid in sorted(inter_e):
mx, my = _node_xy(mid)
axR.add_patch(Circle((mx, my), 0.085, facecolor=COL_SLATE_400,
edgecolor=COL_SLATE_500, linewidth=1.0, zorder=7))
for node in _POS_e:
x, y = big_pos[node]
_draw_node_e(axR, x, y, node, delta_e[node],
fc=(COL_AMBER_100 if node == SRC_e else COL_BG),
ec=(COL_ACCENT if node == SRC_e else COL_PRIMARY))
_edge_lbl = {("a", "b"): "3 parça (2 ara)", ("a", "c"): "tek (0 ara)",
("b", "d"): "2 parça (1 ara)", ("c", "d"): "5 parça (4 ara)"}
for (u, v), lbl in _edge_lbl.items():
x0, y0 = big_pos[u]
x1, y1 = big_pos[v]
mx, my = (x0 + x1) * 0.5, (y0 + y1) * 0.5
ddx, ddy = x1 - x0, y1 - y0
nrm = (ddx * ddx + ddy * ddy) ** 0.5 or 1.0
pxn, pyn = -ddy / nrm, ddx / nrm
axR.text(mx + pxn * 0.30, my + pyn * 0.30, lbl, ha="center", va="center",
fontsize=7.4, color=COL_SLATE_500, zorder=9)
axR.text(big_pos[SRC_e][0], big_pos[SRC_e][1] - _R_e - 0.30, "kaynak s = a",
ha="center", va="center", fontsize=9, color=COL_AMBER_700, weight="bold", zorder=9)
axR.set_title("Kenar-bölünmüş: AĞIRLIKSIZ çizge · BFS seviye rozetleri (AYNI)",
color=COL_TEXT, fontsize=12, weight="bold")
axR.text(1.0, -1.62,
"bedel: Σw = %d yeni düğüm — sayılar büyükse çizge PATLAR\n"
"(pseudopolinom bedel · Ders 27 köprüsü)" % sigma_w_e,
ha="center", va="center", fontsize=8.4, color=COL_AMBER_700, weight="bold", zorder=9)
axR.set_xlim(-0.7, 2.7)
axR.set_ylim(-1.85, 1.55)
axR.set_aspect("equal")
axR.axis("off")
fig.suptitle(
"R2 redüksiyonu: tamsayı-ağırlık → ağırlıksız · bfs(bölünmüş) == dijkstra(orijinal)",
color=COL_TEXT, fontsize=12.5, weight="bold", y=0.99)
plt.tight_layout(rect=(0, 0, 1, 0.95))
plt.show()
```
## 10. NP-complete Örnekleri {#sec-10-np-complete-ornekleri}
NP-tam problemler her yerde:
- **Optimizasyon/sayı:** subset sum (pseudopoli en iyisi), 3-partition, knapsack, **TSP** (gezgin satıcı: tüm düğümleri gezen en kısa yol).
- **Çizge:** en uzun **basit** yol, **3-renklendirme** (2 polinom!), maksimum klik.
- **Mantık:** **SAT / 3-SAT** (Boole formülünü doğru yapan atama var mı).
- **Oyun/bulmaca:** Minesweeper, Sudoku, Super Mario, Zelda, Pokemon (bazıları P-space, NP'den de zor).
**EXP-complete:** $n \times n$ satranç (iki-oyunculu doğası gereği). (LCS de **n dizi** ile NP-tam olur; sabit sayı dizi polinom.)
@fig-np-complete-zoo bu kataloğu bir kart-galerisi olarak dizer: dört kategori sütunu (sayı, çizge, mantık, oyun/bulmaca) altında $12$ NP-tam problem, her biri "NP-tam" rozetli. Üç kontrast rozeti NP-tam'ın **ince çizgisini** vurgular: "3-renklendirme NP-tam ama 2-renklendirme polinom", "en uzun basit yol NP-tam ama en kısa yol polinom", "subset sum pseudopolinom var ama gerçek polinom yok ($P \neq NP$ ise)". Sağ altta EXP-complete kutusu ($n \times n$ satranç, iki-oyunculu) ve LCS'in $n$-dizi notu; alt şerit "$P \neq NP$ ise hiçbiri polinom-zamanda çözülemez (yaklaşık/sezgisel/SAT-solver'a git)".
```{python}
#| label: fig-np-complete-zoo
#| fig-cap: "NP-tam Hayvanat Bahçesi (Demaine L19 §10 İMZA): NP-tam problemler her yerde. 4 kategori sütunu kart-galerisi (her kart 'NP-tam' rozetli, mini kavramsal ikon, SAYI YOK): SAYI (subset sum 'pseudopolinom en iyisi', 3-partition, knapsack, TSP), ÇİZGE (en uzun BASİT yol, 3-renklendirme, maksimum klik), MANTIK (SAT / 3-SAT), OYUN/BULMACA (Minesweeper, Sudoku, Super Mario, Tetris). KONTRAST rozetleri — küçük bir değişiklik P ↔ NP-tam'ı ayırır: 3-renklendirme NP-tam AMA 2-renklendirme POLİNOM · en uzun BASİT yol NP-tam AMA en kısa yol POLİNOM · subset sum pseudopolinom VAR AMA gerçek polinom YOK (P ≠ NP ise). EXP-complete kutusu (sağ alt): n×n satranç (iki-oyunculu doğası gereği, EXP'de P'de DEĞİL) + 'LCS sabit dizi polinom ama n DİZİ ile NP-tam'. Alt şerit: P ≠ NP ise hiçbiri polinom-zamanda çözülemez (yaklaşık/sezgisel/SAT-solver'a git). KAVRAMSAL figür (assert): 4 kategori [4,3,1,4] = 12 NP-tam problem L19 §10 birebir; 3 kontrast çifti; EXP-complete satranç ayrı."
#| fig-width: 12.0
#| fig-height: 6.6
# fig-np-complete-zoo (L19 §10 İMZA): NP-tam katalog. KAVRAMSAL — sayı yok.
_ZOO = {
"SAYI": {"cards": [("subset sum", "set"), ("3-partition", "set"),
("knapsack", "bag"), ("TSP", "tour")]},
"ÇİZGE": {"cards": [("en uzun BASİT yol", "path"), ("3-renklendirme", "color"),
("maksimum klik", "clique")]},
"MANTIK": {"cards": [("SAT / 3-SAT", "sat")]},
"OYUN / BULMACA": {"cards": [("Minesweeper", "mine"), ("Sudoku", "sudoku"),
("Super Mario", "mario"), ("Tetris", "tetris")]},
}
_CAT_ORDER = ["SAYI", "ÇİZGE", "MANTIK", "OYUN / BULMACA"]
_CONTRASTS = [
"3-renklendirme NP-tam AMA 2-renklendirme POLİNOM",
"en uzun BASİT yol NP-tam AMA en kısa yol POLİNOM",
"subset sum: pseudopolinom VAR AMA gerçek polinom YOK (P ≠ NP ise)",
]
assert _CAT_ORDER == ["SAYI", "ÇİZGE", "MANTIK", "OYUN / BULMACA"]
assert [len(_ZOO[c]["cards"]) for c in _CAT_ORDER] == [4, 3, 1, 4]
assert len(_CONTRASTS) == 3
_all_names = [nm for c in _CAT_ORDER for (nm, _i) in _ZOO[c]["cards"]]
assert len(_all_names) == 12
for _need in ("subset sum", "TSP", "3-renklendirme", "en uzun BASİT yol",
"SAT / 3-SAT", "Tetris"):
assert _need in _all_names, _need
def _icon(ax, kind, cx, cy, s=0.16):
if kind == "set":
for dx in (-s, 0, s):
ax.add_patch(Circle((cx + dx, cy), s * 0.32, fc=COL_AMBER_300,
ec=COL_AMBER_700, lw=0.9, zorder=6))
elif kind == "bag":
ax.add_patch(FancyBboxPatch((cx - s, cy - s), 2 * s, 1.7 * s,
boxstyle="round,pad=0.005,rounding_size=0.03",
fc=COL_AMBER_100, ec=COL_AMBER_700, lw=1.1, zorder=6))
ax.plot([cx - s * 0.5, cx + s * 0.5], [cy + s * 0.75, cy + s * 0.75],
color=COL_AMBER_700, lw=1.4, zorder=7)
elif kind == "tour":
pts = [(cx - s, cy - s * 0.7), (cx + s, cy - s * 0.7),
(cx + s * 0.6, cy + s), (cx - s * 0.6, cy + s)]
for i in range(len(pts)):
a, b = pts[i], pts[(i + 1) % len(pts)]
ax.plot([a[0], b[0]], [a[1], b[1]], color=COL_AMBER_600, lw=1.1, zorder=5)
for px, py in pts:
ax.add_patch(Circle((px, py), s * 0.22, fc=COL_BG, ec=COL_PRIMARY, lw=0.9, zorder=6))
elif kind == "path":
xs = [cx - s, cx - s * 0.3, cx + s * 0.4, cx + s]
ys = [cy - s * 0.6, cy + s * 0.5, cy - s * 0.5, cy + s * 0.6]
for i in range(len(xs) - 1):
ax.plot([xs[i], xs[i + 1]], [ys[i], ys[i + 1]], color=COL_AMBER_600, lw=1.4, zorder=5)
for px, py in zip(xs, ys):
ax.add_patch(Circle((px, py), s * 0.20, fc=COL_BG, ec=COL_PRIMARY, lw=0.9, zorder=6))
elif kind == "color":
cols = [COL_ACCENT, COL_PRIMARY, COL_AMBER_300]
pts = [(cx - s, cy - s * 0.5), (cx + s, cy - s * 0.5), (cx, cy + s)]
for i in range(3):
ax.plot([pts[i][0], pts[(i + 1) % 3][0]], [pts[i][1], pts[(i + 1) % 3][1]],
color=COL_SLATE_400, lw=0.9, zorder=5)
for (px, py), c in zip(pts, cols):
ax.add_patch(Circle((px, py), s * 0.28, fc=c, ec=COL_PRIMARY, lw=0.9, zorder=6))
elif kind == "clique":
pts = [(cx - s, cy - s), (cx + s, cy - s), (cx + s, cy + s), (cx - s, cy + s)]
for i in range(4):
for j in range(i + 1, 4):
ax.plot([pts[i][0], pts[j][0]], [pts[i][1], pts[j][1]],
color=COL_AMBER_600, lw=0.8, zorder=5)
for px, py in pts:
ax.add_patch(Circle((px, py), s * 0.20, fc=COL_AMBER_100, ec=COL_AMBER_700, lw=0.9, zorder=6))
elif kind == "sat":
ax.text(cx, cy, "∧∨¬", ha="center", va="center", fontsize=10,
color=COL_AMBER_700, weight="bold", zorder=6)
elif kind == "mine":
for i in range(3):
for j in range(2):
ax.add_patch(FancyBboxPatch(
(cx - s + i * s * 0.7, cy - s * 0.5 + j * s * 0.7), s * 0.6, s * 0.6,
boxstyle="square,pad=0", fc=COL_BG, ec=COL_SLATE_400, lw=0.7, zorder=5))
ax.add_patch(Circle((cx, cy - s * 0.2 + s * 0.35), s * 0.18,
fc=COL_ACCENT, ec=COL_AMBER_700, lw=0.8, zorder=6))
elif kind == "sudoku":
for i in range(4):
ax.plot([cx - s, cx + s], [cy - s + i * 2 * s / 3] * 2, color=COL_SLATE_400, lw=0.7, zorder=5)
ax.plot([cx - s + i * 2 * s / 3] * 2, [cy - s, cy + s], color=COL_SLATE_400, lw=0.7, zorder=5)
ax.text(cx - s * 0.55, cy - s * 0.45, "?", ha="center", va="center",
fontsize=7, color=COL_AMBER_700, weight="bold", zorder=6)
elif kind == "mario":
ax.plot([cx - s, cx + s], [cy - s * 0.8, cy - s * 0.8], color=COL_PRIMARY, lw=1.6, zorder=5)
ax.plot([cx - s * 0.6, cx, cx + s * 0.5], [cy - s * 0.8, cy + s, cy - s * 0.4],
color=COL_ACCENT, lw=1.2, zorder=6)
ax.add_patch(Circle((cx + s * 0.5, cy - s * 0.4), s * 0.16, fc=COL_AMBER_300, ec=COL_AMBER_700, lw=0.7, zorder=7))
elif kind == "tetris":
for ox, oy in [(-1, 0), (0, 0), (1, 0), (0, 1)]:
ax.add_patch(FancyBboxPatch(
(cx + ox * s * 0.7 - s * 0.32, cy + oy * s * 0.7 - s * 0.32), s * 0.64, s * 0.64,
boxstyle="square,pad=0", fc=COL_ACCENT, ec=COL_AMBER_700, lw=0.7, zorder=6))
else:
ax.add_patch(Circle((cx, cy), s * 0.5, fc=COL_BG, ec=COL_PRIMARY, lw=0.9, zorder=6))
def _draw_column(ax, cat, x0, top_y, col_w):
cards = _ZOO[cat]["cards"]
head_h = 0.52
ax.add_patch(FancyBboxPatch(
(x0, top_y - head_h), col_w, head_h, boxstyle="round,pad=0.02,rounding_size=0.08",
fc=COL_PRIMARY, ec=COL_PRIMARY, lw=1.5, zorder=3))
ax.text(x0 + col_w * 0.5, top_y - head_h * 0.5, cat, ha="center", va="center",
fontsize=11, color=COL_WHITE, weight="bold", zorder=5)
card_h, gap = 0.78, 0.18
y = top_y - head_h - 0.22
for name, icon in cards:
ax.add_patch(FancyBboxPatch(
(x0, y - card_h), col_w, card_h, boxstyle="round,pad=0.02,rounding_size=0.07",
fc=COL_BG, ec=COL_AMBER_700, lw=1.6, zorder=3))
icx, icy = x0 + 0.36, y - card_h * 0.5
_icon(ax, icon, icx, icy)
ax.add_patch(FancyBboxPatch(
(x0 + col_w - 0.78, y - 0.30), 0.70, 0.24, boxstyle="round,pad=0.01,rounding_size=0.05",
fc=COL_AMBER_100, ec=COL_ACCENT, lw=1.1, zorder=5))
ax.text(x0 + col_w - 0.43, y - 0.18, "NP-tam", ha="center", va="center",
fontsize=6.5, color=COL_AMBER_700, weight="bold", zorder=6)
ax.text(x0 + 0.66, icy + 0.02, name, ha="left", va="center",
fontsize=9.0, color=COL_TEXT, weight="bold", zorder=6)
if name == "subset sum":
ax.text(x0 + 0.66, icy - 0.22, "pseudopolinom en iyisi", ha="left",
va="center", fontsize=6.3, color=COL_SLATE_500, style="italic", zorder=6)
y -= (card_h + gap)
def _draw_contrasts(ax, x0, y0, w):
ax.add_patch(FancyBboxPatch(
(x0, y0 - 1.62), w, 1.62, boxstyle="round,pad=0.03,rounding_size=0.10",
fc=COL_WHITE, ec=COL_ACCENT, lw=2.2, zorder=3))
ax.text(x0 + w * 0.5, y0 - 0.26, "KONTRAST — küçük bir değişiklik P ↔ NP-tam'ı ayırır",
ha="center", va="center", fontsize=9.5, color=COL_AMBER_700, weight="bold", zorder=5)
yy = y0 - 0.66
for line in _CONTRASTS:
ax.add_patch(Polygon(
[(x0 + 0.22, yy - 0.06), (x0 + 0.40, yy - 0.06), (x0 + 0.31, yy + 0.12)],
closed=True, fc=COL_ACCENT, ec=COL_AMBER_700, lw=0.8, zorder=5))
ax.text(x0 + 0.31, yy + 0.01, "!", ha="center", va="center", fontsize=6,
color=COL_WHITE, weight="bold", zorder=6)
ax.text(x0 + 0.56, yy + 0.01, line, ha="left", va="center",
fontsize=8.6, color=COL_TEXT, zorder=5)
yy -= 0.40
def _draw_exp_box(ax, x0, y0, w, h):
ax.add_patch(FancyBboxPatch(
(x0, y0 - h), w, h, boxstyle="round,pad=0.03,rounding_size=0.10",
fc=COL_AMBER_100, ec=COL_AMBER_700, lw=2.4, zorder=3))
ax.text(x0 + w * 0.5, y0 - 0.26, "EXP-complete (NP'den de zor)",
ha="center", va="center", fontsize=9.5, color=COL_AMBER_700, weight="bold", zorder=6)
cell = 0.155
board = 4 * cell
bx = x0 + 0.28
by = y0 - 0.54 - board
for i in range(4):
for j in range(4):
if (i + j) % 2 == 0:
ax.add_patch(FancyBboxPatch(
(bx + i * cell, by + j * cell), cell, cell, boxstyle="square,pad=0",
fc=COL_PRIMARY, ec=COL_PRIMARY, lw=0, zorder=5))
ax.add_patch(FancyBboxPatch(
(bx, by), board, board, boxstyle="square,pad=0", fc="none", ec=COL_AMBER_700, lw=1.4, zorder=6))
ax.text(bx + board * 0.5, by - 0.17, "n×n satranç", ha="center", va="center",
fontsize=8.5, color=COL_TEXT, weight="bold", zorder=6)
tx = bx + board + 0.30
ax.text(tx, by + board * 0.62, "iki-oyunculu doğası gereği", ha="left", va="center",
fontsize=8.0, color=COL_TEXT, zorder=6)
ax.text(tx, by + board * 0.20, "EXP'de, P'de DEĞİL (kanıtlı)", ha="left", va="center",
fontsize=8.0, color=COL_SLATE_500, zorder=6)
ax.text(x0 + w * 0.5, y0 - h + 0.16,
"Not: LCS sabit dizi sayısıyla polinom — ama n DİZİ ile NP-tam olur.",
ha="center", va="center", fontsize=7.2, color=COL_SLATE_500, style="italic", zorder=6)
fig, ax = plt.subplots(figsize=(12.0, 6.6))
fig.patch.set_facecolor(COL_WHITE)
col_w, col_gap = 2.55, 0.30
x = 0.0
top_y = 5.55
for cat in _CAT_ORDER:
_draw_column(ax, cat, x, top_y, col_w)
x += col_w + col_gap
total_w = x - col_gap
panel_top = 0.62
_draw_contrasts(ax, 0.0, panel_top, col_w * 2 + col_gap + 1.40)
exp_w = col_w + col_gap + 0.85
exp_h = 1.85
_draw_exp_box(ax, total_w - exp_w, panel_top, exp_w, exp_h)
strip_y = panel_top - max(1.62, exp_h) - 0.30
ax.add_patch(FancyBboxPatch(
(0.0, strip_y - 0.52), total_w, 0.52, boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_PRIMARY, ec=COL_PRIMARY, lw=1.5, zorder=3))
ax.text(total_w * 0.5, strip_y - 0.26,
"P ≠ NP ise: hiçbiri polinom-zamanda çözülemez "
"(yaklaşık / sezgisel / SAT-solver'a git)",
ha="center", va="center", fontsize=11, color=COL_WHITE, weight="bold", zorder=6)
fig.suptitle(
"NP-tam Hayvanat Bahçesi — NP-tam problemler her yerde (L19 §10, Demaine)",
color=COL_TEXT, fontsize=13.5, weight="bold", y=0.975)
ax.set_xlim(-0.3, total_w + 0.3)
ax.set_ylim(-2.35, top_y + 0.35)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout(rect=(0, 0, 1, 0.95))
plt.show()
```
## Bu Dersin Özeti {#sec-bu-dersin-ozeti-d28}
1. **$P \subseteq NP \subseteq EXP \subseteq R$**; $P \neq EXP$ kesin; $P = NP$ açık (1 M\$).
2. **Halting problem** $R$ dışında (uncomputable); çoğu problem çözülemez (countable program vs uncountable problem).
3. **NP** = şanslı algoritma (hep doğru tahmin) = certificate'le polinom-doğrulanabilir.
4. **Asimetri**: "evet" ispatlanabilir, "hayır" değil.
5. **$P \neq NP$** (varsayım): "şans engineer edilemez"; ispat bulmak doğrulamaktan zor.
6. **NP-hard** = NP kadar zor; **NP-complete** = $NP \cap NP\text{-hard}$ (NP'nin en zoru).
7. **Reduction**: bilinen-zor problemi hedefe indirge → zorluk kanıtı (3-partition → Tetris).
::: {.callout-important title="Tek Bir Cümle"}
$P$ (verimli çözülebilir) $\subseteq NP$ (verimli doğrulanabilir) $\subseteq EXP \subseteq R$; çoğu problem $R$'nin bile dışındadır; NP-tam problemler (Tetris, TSP, 3-SAT) NP'nin en zorudur ve bir problemi NP-tam bir probleme indirgeyerek "$P \neq NP$ ise verimli çözülemez" kanıtlanır.
:::
## Kontrol Soruları {#sec-kontrol-sorulari-d28}
::: {.callout-note collapse="true" title="Soru 1: «Çoğu problem çözülemez» iddiası hangi sayma argümanına dayanır?"}
**Cevap:**
Bir **program** sonlu bir bit dizisidir → bir doğal sayıya karşılık gelir; doğal sayılar **sayılabilir (countable)**. Bir **karar problemi** ise, her olası girdi (sonsuz girdi) için bir yes/no belirtir → sonsuz bir bit dizisi → $[0, 1]$ aralığında bir **reel sayı**; reel sayılar **sayılamaz (uncountable)**. Sayılamaz çokluk, sayılabilirden "kat kat fazladır" — yani problem sayısı, program sayısından çok daha fazla. Her program en fazla bir problemi çözdüğünden, problemlere yetecek program **yoktur** → çoğu problem çözülemez (uncomputable). (Neyse ki önemsediğimiz çoğu problem $R$'dedir.)
:::
::: {.callout-note collapse="true" title="Soru 2: NP'nin iki tanımı (şanslı algoritma / doğrulayıcı) nasıl eşdeğer, ve «asimetri» nedir?"}
**Cevap:**
**Şanslı algoritma:** tahmin yapan, bir "evet"e götüren yol varsa hep doğru tahmin eden polinom-zaman algoritması. **Doğrulayıcı:** girdi + certificate alıp polinom-zamanda kontrol eden algoritma. Eşdeğerlik: şanslı algoritmanın "doğru tahminleri" tam olarak certificate'tır — tahminleri yazarsan certificate olur; certificate verilirse doğrulayıcı onu "tahmin gibi" kontrol eder. **Asimetri:** her ikisi de yalnız "**evet**" cevaplarını garanti eder — evet için certificate vardır/doğrulayıcı evet der; ama "hayır" için kısa bir kanıt yoktur (subset sum'da "bu sayı temsil edilemez"i ispatlamanın bilinen kısa yolu yok). Bu yüzden Tetris'i "hayatta kalınabilir mi?" diye tanımlamak NP'dedir, "kalınamaz mı?" değil.
:::
::: {.callout-note collapse="true" title="Soru 3: Reduction ile zorluk nasıl kanıtlanır? A ≤ B neyi ima eder?"}
**Cevap:**
A'dan B'ye bir reduction (A girdisini B girdisine, B çözümünü A çözümüne çeviren), "**A en az B kadar kolaydır**" der (B'yi çözebilirsem A'yı da çözerim). Mantıksal karşıt-tersi: "**B en az A kadar zordur**". Zorluk kanıtı için: **bilinen NP-tam bir problemi** (A $=$ 3-partition) **hedef probleme** (B $=$ Tetris) indirgeriz; bu, "Tetris en az 3-partition kadar zor" $=$ Tetris NP-hard demektir. Yani Tetris için polinom algoritma olsaydı, 3-partition (ve dolayısıyla tüm NP) polinom-zamanda çözülürdü → $P = NP$. $P \neq NP$ varsayımıyla, Tetris polinom-zamanda çözülemez.
:::
::: {.callout-note collapse="true" title="Soru 4: P, NP, EXP, R, NP-hard, NP-complete sınıfları zorluk ekseninde nasıl konumlanır?"}
**Cevap:**
Tek bir "zorluk" ekseni düşün (solda kolay, sağda zor). **P** (en solda küçük segment), **NP** (P'yi içerir, biraz daha geniş), **EXP** (NP'yi içerir), **R** (EXP'yi içerir, sonlu-zaman) — hepsi **üst sınır** ("bu çizginin solundasın"). **NP-hard** bir **alt sınır**dır ("şu noktanın sağındasın" — NP'nin en zorundan itibaren sağa, sonsuza). **NP-complete** $= NP \cap NP\text{-hard}$, yani NP'nin tam sağ ucu (hem NP'de hem NP kadar zor; Tetris, TSP). **EXP-complete** $=$ EXP'nin sağ ucu ($n \times n$ satranç). $P = NP$ olup olmadığını bilmediğimizden, P ile NP arası "boşluk" var mı kesin değil — ama $P \neq EXP$ kesin.
:::
## Egzersizler {#sec-egzersizler-d28}
**Egzersiz 1.** P, NP, EXP, R sınıflarını birer örnek problemle eşle; her birinin "üst sınır" mı "alt sınır" mı belirttiğini yaz.
**Egzersiz 2.** Halting problem'in neden uncomputable olduğunu, "çoğu problem çözülemez" sayma argümanıyla ilişkilendir.
**Egzersiz 3.** NP'nin iki tanımının (şanslı algoritma / doğrulayıcı) Tetris üzerinde nasıl çalıştığını adım adım yaz.
**Egzersiz 4.** 3-partition → Tetris indirgemesinin neden Tetris'i NP-hard yaptığını, $A \le B$ mantığıyla açıkla.
**Egzersiz 5.** Verilen bir optimizasyon problemini (örn. TSP) karar problemine çevir ($\le x$ var mı) ve ikili aramayla optimumun nasıl bulunacağını göster.
## Sonraki Ders İçin Hazırlık {#sec-sonraki-ders-icin-hazirlik-d28}
::: {.callout-warning title="Sonraki: Ders 29 (PS9) — Problem Oturumu 9 (Justin Solomon)"}
**Ders 29 (PS9): Problem Oturumu 9** (karmaşıklık + genel tekrar). Hoca değişir: bu oturumu **Justin Solomon** yürütür (Demaine'in ders dizisinden farklı). Bir problem oturumuyla, gördüğümüz tüm konuları (özellikle karmaşıklık ve indirgeme) gerçek problemlerde pekiştiriyoruz. P/NP ayrımı, NP-hardness kanıtı ve reduction sezgisi merkezde.
**Ders 29 Öncesi Yapılacak:**
- Bu dersin egzersizlerini, özellikle Egzersiz 3 (NP iki tanım) ve 4 (reduction) çöz.
- P/NP/EXP/R hiyerarşisini ve NP-hard/NP-complete ayrımını ezberden çiz.
- Ana cümleyi tekrar oku: *"Bilinen-zor problemi hedefe indirge → zorluk kanıtı; şans engineer edilemez."*
:::
## Anahtar Kavramlar (Cheat Sheet) {#sec-anahtar-kavramlar-d28}
| Kavram | Tanım | Sayfada |
|---|---|---|
| **P** | Polinom-zaman çözülebilir; "verimli" | Böl. 2 |
| **NP** | Şanslı algoritma / certificate'le doğrulanabilir | Böl. 5-6 |
| **EXP / R** | Üstel-zaman / sonlu-zaman; $P \subseteq NP \subseteq EXP \subseteq R$ | Böl. 2 |
| **Uncomputable** | $R$ dışı (halting); çoğu problem böyle | Böl. 3-4 |
| **$P \neq NP$** | Varsayım; "şans engineer edilemez" | Böl. 7 |
| **NP-hard** | NP kadar zor (alt sınır); her NP buna indirger | Böl. 8 |
| **NP-complete** | $NP \cap NP\text{-hard}$; Tetris, TSP, 3-SAT | Böl. 8, 10 |
| **Reduction** | $A \le B \to B$ en az $A$ kadar zor; zorluk kanıtı | Böl. 9 |
## Builder ve OMSCS Bağlantıları {#sec-builder-ve-omscs-baglantilari-d28}
::: {.callout-tip title="6 köprü"}
Bu dersin sınıf hiyerarşisi, NP'nin iki tanımı ve reduction aracı, sistem mühendisliği, kriptografi ve graduate algoritmalarındaki çok sayıda araca bağlanır; köprülerin özeti:
1. **$P \neq NP$** $\to$ **kriptografi/güvenlik** temeli (RSA, hash); "tek yön kolay, ters zor" — modern şifreleme bu konjektürün doğru olduğuna bahse girer.
2. **NP-complete farkındalığı** $\to$ TSP, scheduling, knapsack; "verimli çözme yok → yaklaşık/sezgisel/**SAT-solver**'a git" (pratikte 3-SAT örnekleri devasa olsa da modern SAT-solver'lar çoğu gerçek örneği çözer).
3. **Reduction** $\to$ problem indirgeme refleksi; bir problemi bildiğin-zor bir probleme oturtmak — **OMSCS CS 6515 NP-tamlık çekirdeği**'nin temel becerisi.
4. **Halting $=$ uncomputable** $\to$ **statik analiz / bug tespiti sınırı**; "tüm sonsuz döngüleri (veya tüm bug'ları) bulan program yoktur" — derleyici ve linter'ların neden eksiksiz olamadığının teorik nedeni.
5. **Certificate / doğrulayıcı** $\to$ blockchain ispatı, **zero-knowledge** kanıt, hızlı doğrulama; "çözmek zor, doğrulamak kolay" asimetrisi (`verify_subset_certificate` NP Tanım-2'nin çalışan örneğidir).
6. **Decision problem** $\to$ optimizasyon $\leftrightarrow$ karar dönüşümü (ikili aramayla); "$\le x$ var mı?" sorusu binary search'le optimumu verir — graduate algoritmalarında sürekli kullanılan dönüşüm.
:::
---
::: {.callout-important title="Tek bir şey alıp gideceksen"}
Problemler zorluk ekseninde sınıflanır: **P** (verimli çözülebilir) $\subseteq$ **NP** (verimli doğrulanabilir) $\subseteq$ **EXP** $\subseteq$ **R** (sonlu-zaman). Çoğu problem $R$'nin bile dışındadır — halting problem gibi **uncomputable** (çünkü reel-sayı-çoklukta problem, doğal-sayı-çoklukta program var). **NP-tam** problemler (Tetris, TSP, 3-SAT) NP'nin en zorudur; bir problemi NP-tam bir probleme **indirgeyerek** "$P \neq NP$ ise verimli çözülemez" kanıtlanır. NP'de "evet" ispatlanabilir ama "hayır" değildir — ve "şans engineer edilemez" ($P \neq NP$), modern güvenliğin dayanağıdır.
:::
