מכונת טיורינג
A computation model with tapes, read/write heads, and a control state.
Bilingual glossary
Terminology is kept consistent across the entire course.
מכריע
A machine that must halt on every input and return accept or reject.
קונפיגורציה
A complete instantaneous description of a machine run: state, tape contents, and head positions.
גרף קונפיגורציות
A graph whose vertices are configurations and whose edges are single legal transitions.
קידוד
A representation of instances, machines, or numbers as strings over a finite alphabet.
זמן פולינומיאלי
A running-time bound by a polynomial in the encoded input length.
DTIME
The class of languages decided by deterministic machines in $O(t(n))$ time.
DSPACE
The class of languages decided by deterministic machines using $O(s(n))$ workspace.
P
The union of all polynomial DTIME classes; languages decidable in polynomial time.
PSPACE
Decision problems solvable with polynomially bounded workspace.
משפט היררכיה
A result showing that more resource (time or space) enables deciding strictly more languages.
ריפוד / ניפוח
Inflating input length without changing the encoded decision.
מכונה אי־דטרמיניסטית
A machine that accepts if at least one computation branch accepts.
עץ חישוב
A tree whose nodes are configurations and whose children represent legal transition choices.
עד / תעודה
A short string that lets a verifier confirm a yes instance.
תעודה
A polynomially bounded witness attached to an instance and checked by a verifier.
מוודא
A polynomial-time machine checking an instance-certificate pair.
NP
Languages with polynomially bounded certificates verifiable in polynomial time.
coNP
Languages whose complements are in NP; no instances are proved by short certificates.
רדוקציה כמהדר מופעים פולינומיאלית
A polynomial-time map $f$ such that $x\in A\iff f(x)\in B$.
רדוקציה
A computable transformation preserving membership.
רדוקציה קנונית
A standard, well-known reduction in the problem network, e.g. from 3SAT to IS.
בעיות שלמות קנוניות
The central NP-complete family (SAT, IS, CLIQUE, TSP, etc.) and the reduction network linking them.
טרנזיטיביות
If $A\le_m^p B$ and $B\le_m^p C$, then $A\le_m^p C$; composing reductions.
סגירות כלפי מטה
If $A\le_m^p B$ and $B\in\mathrm P$, then $A\in\mathrm P$; same idea for NP and coNP.
NP-קשה
At least as hard as every language in NP under the stated reduction; need not be in NP.
NP-שלמה
A problem in NP to which every NP problem reduces.
משפט Cook–Levin
SAT is NP-complete; every NP language reduces to it via a computation tableau.
טבלת חישוב
A matrix whose rows are full configurations of a machine on a given input.
גאדג׳ט
A subcomponent in a reduction encoding a local constraint (clause, variable, edge).
הוכחת אם־ורק־אם
A two-direction proof: yes in the target $\iff$ yes in the source.
CNF / צורה נורמלית קונjunctive
A Boolean formula as a product of clauses (ORs of literals).
3SAT
SAT where every clause has exactly three literals.
קבוצה בלתי־תלויה (IS)
In a graph: a set of vertices with no edges between them.
קליקה
In a graph: a set of vertices pairwise adjacent.
כיסוי קודקודים (VC)
A vertex set touching every edge at least once.
משלים גרף
A graph with the same vertices and inverted edges: $\{u,v\}\in E(\overline G)\iff\{u,v\}\notin E(G)$.
הכרעה מול אופטימיזציה
A decision problem returns one bit; an optimization problem asks for the solution or objective value.
זמן פסאודו־פולינומיאלי
Polynomial in numeric values but exponential in binary encoding length.
NP-קושי בחוזקה
Hardness that persists even when numeric values are polynomially bounded.
יחס קירוב
A bound comparing an algorithmic solution with the optimum.
היוריסטיקה
A method that works well in practice but lacks approximation or optimality guarantees.
מכונת טיורינג הסתברותית
A machine with access to random bits; after choosing $r$ the run is deterministic.
מונטה קרלו
A randomized algorithm with fixed runtime that may err with bounded probability.
לאס וגאס
A randomized algorithm always correct; runtime is random with bounded expectation.
BPP
Polynomial-time randomized decision with bounded two-sided error.
הגברה
Reducing error probability by repeating a randomized algorithm.
L
Languages decidable in $O(\log n)$ workspace.
NL
Languages decided nondeterministically in logarithmic space.
STCON
Reachability: is there a path from $s$ to $t$ in a directed graph?
רדוקציה במקום לוגריתמי
A reduction computing output without storing it fully; a logarithmic-space transducer.
טרנסדיוסר
A machine that prints output while staying within a space bound.
גרף מרומז
A graph not stored explicitly; adjacency is generated or checked on demand.
משפט סביץ'
$\mathrm{NSPACE}(s(n))\subseteq\mathrm{DSPACE}(s(n)^2)$; in particular $\mathrm{NL}\subseteq\mathrm L$.
אורקל
A black-box language query answered in one computation step.
ההיררכיה הפולינומיאלית (PH)
Classes $\Sigma_k^P$ and $\Pi_k^P$ with $k$ alternating blocks of existential and universal quantifiers.
רלטיביזציה
A proof technique valid relative to every oracle; it limits separation methods.
P/poly
Languages decidable by non-uniform polynomial-size circuits.
מעגל בוליאני
A network of AND, OR, NOT gates computing a Boolean function.