Title: Theory / Unimportant / CS / Fundamental / Complexity / Complexity Arora Barak/{ / Basics
Tags: fromMath mathToDef mathToSee automaticImplies examplesSwitchExample1 toBinaryRelation hasSeenConjDef typToBinary

Definition: There exists a constant \(c\) such that \(f(n)\le cg(n)\) for every sufficiently large \(n\).
Page: 003
Chapter: 0
Variables: \(f,g:\mathbb N\to\mathbb N\).
Notation: \(f=O(g)\)
Index: 2
Kind: Def

Definition: \(g=O(f)\).
Page: 004
Chapter: 0
Variables: \(f,g:\mathbb N\to\mathbb N\).
Notation: \(f=\Omega(g)\)
Index: 2
Kind: Def

Definition: \(f=O(g)\) and \(g=O(f)\).
Page: 004
Chapter: 0
Variables: \(f,g:\mathbb N\to\mathbb N\).
Notation: \(f=\Theta(g)\)
Index: 2
Kind: Def

Definition: For every \(\epsilon>0\), for \(n\) big enough \(f(n)\le \epsilon g(n)\).
Page: 004
Chapter: 0
Variables: \(f,g:\mathbb N\to\mathbb N\).
Notation: \(f=o(g)\)
Index: 2
Kind: Def

Definition: \(g=o(f)\).
Page: 004
Chapter: 0
Variables: \(f,g:\mathbb N\to\mathbb N\).
Notation: \(f=\omega(g)\)
Index: 2
Kind: Def

Name: Turing Machine
Definition: A tuple \((\Gamma,Q,\delta)\) where \(\Gamma\) is a finite set of symbols. It is assumed to contains \(\square\), \(\triangleright\) 0 and 1. \(Q\) is a finite set of state containing at least \(q_{start}\) and \(q_{halt}\). And a function \(\delta:Q\times\Gamma^k\to Q\times \Gamma^{k-1}\times \{L,S,R\}^k\) where \(k\ge2\), called the transition function of \(M\).
Page: 004
Chapter: 0
Index: 2
Kind: Def

Name: \(M\) computes \(f\)
Definition: for every \(x\in\{0,1\}^*\), whenever \(M\) is initialized to the start configuration on input \(x\), then it halts with \(f(x)\) written on its output tape.
Page: 015
Chapter: 1
Section: 3
Variables: \(f:\{0,1\}^*\to\{0,1\}^*\)
\(T:\mathbb N\to\mathbb N\) be some functions,
\(M\) be a Turing machine.
Kind: Def

Name: \(M\) computes \(f\) in \(T(n)\)-time
Definition: The computation of \(M\) on every input \(x\) requires at most \(T(|x|)\) steps.
Page: 015
Chapter: 1
Section: 3
Variables: \(f:\{0,1\}^*\to\{0,1\}^*\)
\(T:\mathbb N\to\mathbb N\) be some functions
\(M\) be a Turing machine.
Kind: Def

Name: Time constructible function
Definition: \(T:\mathbb N\to\mathbb N\) such that \(T(n)\ge n\) and there is a TM \(M\) that computes the function \(x\mapsto T(|x|)\) in time \(T(n)\).
Page: 016
Chapter: 1
Index: 3

Question: Every multi-tape Turing machine can be simulated with a polynomial loss of time by
Answer: a single tape oblivious TM
Page: 017
Chapter: 1
Index: 3.1

Name: An oblivious TM
Definition: A TM such that the move of the head does not depends on the input, but only of its length.
Page: 018
Chapter: 1
Variables: \(M\) a TM.
Index: 7
Kind: Rem

Smaller0: there exists a TM \(\mathcal U\) such that for every \(x,\alpha\in\{0,1\}^*\), \(\mathcal (x,\alpha)\)
Greater0: \(M_\alpha(x)\), where \(M_\alpha\) denotes the TM represented by \(\alpha\)
Page: 020
Chapter: 1
Section: 4.1
Index: 9
Kind: Theo
Smaller to greater: equals
Hide middle: yes
Greater1: \(CT\log T\) steps, where \(C\) is a number independent of \(|x|\) and depending only on \(M_\alpha\)'s alphabet size, number of tapes and number of states
Connect Greater0: and if \(M_\alpha\) halts on input \(x\) within \(T\) steps then \(\mathcal U(x,\alpha)\) halts within

Name: Uncomputable function
Page: 022
Chapter: 1
Section: 4.1
Index: 10
Kind: Theo
Example: \(UC\) wich sends \(\alpha\) to 0 if \(M_\alpha(\alpha)=1\) and 1 otherwise
Extra: Non défini

Definition: \(\bigcup_{c\in\mathbb N}\pmb{NTIME}(n^c)\)
Page: 41
Chapter: 2
Section: 1.2
Notation: \(\pmb{NP}\)
Index: 6
Kind: Theo

Name: A non deterministic turing machine (NDTM)
Definition: A Turing machine with a second transition function.
Page: 041
Chapter: 2
Section: 1.2

Page: 042
Definition: A language \(L'\) such that there exists a polynomial-time computable function \(f:\{0,1\}^*\to\{0,1\}^*\) such that for every \(x\in\{0,1\}^*\), \(x\in L\) iff \(f(x)\in L'\).
Chapter: 2
Variables: \(L\subseteq \{0,1\}^*\) a language.
Name: A language polynomial-time Karp/mapping reducible to \(L\)
Kind: Def
Index: 7
Name2: A language many-to-one reducible to \(L\)
Order: Partial

Page: 042
Definition: \(L'\) is polynomyal-time mapping reducible to \(L\)
Chapter: 2
Variables: \(L,L'\subseteq \{0,1\}^*\) languages.
Notation: \(L\le_p L'\)
Kind: Def
Index: 7

Name: NP-hard language
Definition: A language such that every NP language is polynomial time reducible to it.
Page: 043
Chapter: 2
Index: 28
Kind: Theorem

Smaller0: \(L'\in P\)
Greater0: \(L\in P\)
Page: 043
Chapter: 2
Variables: \(L,L'\subseteq \{0,1\}^*\) a language.
Index: 8
Kind: Theo
Assuming: \(L\le _p L'\)
Hide sides: yes

Smaller0: \(L\) belongs to P
Greater0: P=NP
Page: 043
Chapter: 2
Variables: \(L\subseteq \{0,1\}^*\) a language.
Index: 8 3
Kind: Theo
Smaller to greater: iff
Assuming: \(L\) is NP-complete

Name: SAT
Definition: Given a propositional formula, does there exists a boolean assignment of the variables satisfying the formula.
Page: 044
Chapter: 2
Section: 3.1

Name: 3SAT
Definition: Given a propositional formula in conjunctive normal form where each disjunction has at most 3 elements, does there exists a boolean assignment of the variables satisfying the formula.
Page: 044
Chapter: 2
Section: 3.1

Name: INDSET
Definition: given a graph \(G\) and an integer \(i\), does \(G\) admits an independant set of cardinal \(i\).
Page: 051
Chapter: 2
Section: 3.1
Index: 15
Kind: Theo

Definition: Given a list of \(m\) linear inequalities with rational coefficient over \(n\) variables, is there an assignment with zeroes and ones of the variables satisfying all inequations.
Page: 052
Chapter: 2
Section: 3.1
Notation: 01 IPROG
Index: 16
Kind: Theo

Name: dHAMPATH
Definition: Given a directed graph, is there an hamiltonian path.
Page: 053
Chapter: 2
Section: 3.1
Index: 17
Kind: Theo

Name: An hamiltonian path of a \(G\)
Definition: A sequence \(n_0,\dots,n_n\), containing each nodes of \(G\) exactly once, such that \((n_i,n_{i+1})\) is a vertex of the graph.
Page: 053
Chapter: 2
Section: 3.1
Variables: \(G\) a directed graph.
Index: 17
Kind: Theo

Name: coNP
Definition: the set of languages whose complement belongs to NP.
Page: 055
Chapter: 2
Section: 6.1
Definition2: it is the set of languages \(L\) such that there exists a polynomial \(p:\mathbb N\to\mathbb N\), and \[x\in L\iff \forall u\in\{0,1\}^{p(|x|)}, M(x,u).\]

Definition: \(\bigcup_{c\ge1}DTIME(2^{n^c})\)
Page: 056
Chapter: 2
Section: 6.2
Notation: EXP

Definition: \(\bigcup_{c\ge1}NTIME(2^{n^c})\)
Page: 056
Chapter: 2
Section: 6.2
Notation: NEXP

Question: \(EXP\ne NEXP\) implies
Answer: \(P\ne NP\)
Page: 057
Chapter: 2
Section: 6.2
Index: 22
Kind: Theo

Smaller0: \(f(n)\log(f(n))=o(g(n))\)
Greater0: \(DTIME(f(n))\subsetneq DTIME(g(n))\)
Page: 069
Chapter: 3
Section: 1
Variables: \(f,g:\mathbb N\to\mathbb N\).
Kind: Theo
Prefix Smaller: \(f,g\) are time-constructible functions satisfying

Smaller0: \(f(n+1)=o(g(n))\)
Greater0: \(NTIME(f(n))\subsetneq NTIME(g(n))\)
Page: 069
Chapter: 3
Section: 2
Variables: \(f,g:\mathbb N\to\mathbb N\).
Kind: Theo
Hide middle: yes
Prefix Smaller: \(f,g\) are time-constructible functions satisfying

Smaller0: \(\mathbf{P}\ne\mathbf{NP}\)
Greater0: there exists a language \(L\in \mathbf{NP}\setminus\mathbf{P}\) that is not \(\mathbf{NP}\)-complete
Page: 071
Chapter: 3
Kind: Theo
Smaller to greater: iff

Q: [...]
[...]
A: The existence of an effective representation of Turing machine by strings; The ability of one TM to simulate any another without much overhead in running time or space.
Page: 073
Chapter: 3
Section: 4
Name: Diagonalization
Conjdef: Either

Name: A Turing machine with oracle \(O\)
Definition: A TM \(M\) that has a special read-write tape we call \(M\)'s oracle tape and three special states \(q_{query}\), \(q_{yes}\) and \(q_{no}\). Whenever during the execution \(M\) enters the state \(q_{query}\), the machine moves into the state \(q_{yes}\) if the content of the oracle tape belongs to \(P\) and \(q_{no}\) otherwise.
Page: 073
Chapter: 3
Variables: \(O\subseteq\{0,1\}^*\).
Index: 4
Kind: Def

Definition: The set containing every language that can be decided by a polynomial-time deterministic TMs with oracle access to \(O\)
Page: 073
Chapter: 3
Section: 4
Variables: \(O\subseteq \{0,1\}^*\).
Notation: \(P^O\)
Index: 5
Kind: Def

Q: [...]
A: the set containing every language that can be decided by a polynomial-time NDTMs with oracle access to \(O\).
Page: 073
Chapter: 3
Section: 5
Variables: \(O\subseteq \{0,1\}^*\)
Kind: Def
Q: [...]
A: \(NP^O\)

Question: Why can't diagonalization be used for P vs NP
Answer: For some oracles \(A\) and \(B\), \(P^A=NP^A\) and \(P^B\ne NP^B\). And diagonalization holds on machines without oracles only if it works on machine with all oracles.
Page: 074
Chapter: 3
Section: 4
Index: 7
Kind: Def

Q: [...]
A: The set of languages \(L\subseteq \{0,1\}^*\) such that there is a constant \(c\) and a TM \(M\) deciding \(L\) such that at most \(c s(n)\) locations on \(M\)'s work tapes, excluding the input tape, are ever visited by \(M\)'s head during its computation on every input of length \(n\).
Page: 078
Chapter: 4
Section: 1
Variables: \(s:\mathbb N\to\mathbb N\)
Kind: Def
Q: [...]
A: \(SPACE (s(n))\)

Name: A language in \(NSPACE (s(n))\)
Definition: A language \(L\) such that there is a constant \(c\) and a NDTM \(M\) deciding \(L\) such at most \(c s(n)\) locations on \(M\)'s work tapes, excluding the input tape, are ever visited by \(M\)'s head during its computation on every input of length \(n\) iff there exists a read-once input tape which contains a certificates.
Page: 078
Chapter: 4
Section: 1
Variables: \(s:\mathbb N\to\mathbb N\) and \(L\subseteq \{0,1\}^*\).
Kind: Def

Smaller0: \[DTIME(S(n))\]
Greater0: \[ SPACE(S(n))\]
Page: 080
Chapter: 4
Section: 1
Variables: \(S:\mathbb N\to\mathbb N\) space constructible.
Index: 2
Kind: Theo
Smaller to greater: \(\subseteq\)
Greater to smaller: \(\supseteq\)

Smaller0: \[S(n)\]
Page: 080
Chapter: 4
Section: 1
Variables: \(S:\mathbb N\to\mathbb N\) space constructible.
Index: 2
Kind: Theo
Smaller to greater: \(\subseteq\)
Prefix Greater: \[ NSPACE(\]
Greater to smaller: \(\supseteq\)
Prefix Smaller: \[SPACE(\]
Suffix Greater: \[)\]

Smaller0: \(NSPACE(S(n))\)
Greater0: \(2^{O(S(n))}\)
Page: 080
Chapter: 4
Section: 1
Variables: \(S:\mathbb N\to\mathbb N\) space constructible.
Index: 2
Kind: Theo
Smaller to greater: \(\subseteq\)
Prefix Greater: \( DTIME(\)
Greater to smaller: \(\supseteq\)
Suffix Greater: \()\)

Name: A configuration of a \(M\)
Definition: A possible content of its tapes, with a position of its head and a state.
Page: 080
Chapter: 4
Section: 1.1
Variables: \(M\) a TM.

Question: Every configuration can be encoded with
Answer: \(cS(n)\) bits where \(c\) depends of the number size of the alphabet and the number of tapes.
Page: 080
Chapter: 4
Section: 1.1
Variables: \(S:\mathbb N\to\mathbb N\)
\(M\) a TM in \(SPACE(M)\).
Kind: Claim

Question: The size of the configuration graph is
Answer: at most \(2^{cS(n)}\), where \(c\) depends of the number size of the alphabet and the number of tapes.
Page: 080
Chapter: 4
Section: 1.1
Variables: \(S:\mathbb N\to\mathbb N\)
\(M\) a TM in \(SPACE(S)\)
Context: TM
Kind: Claim

Definition: holding when \(C\) and \(C'\) encode two neighboring configurations in \(G_{M,x}\)
Page: 080
Chapter: 4
Section: 1.1
Variables: \(M\) be a machine
\(x\) an input.
\(C,C'\) strings
Context: configuration graph
Notation: \(\phi_{M,x}(C,C')\)
Kind: Claim
Definition2: of size \(O(s(n))\)
Conjdef: A CNF-formula
Extra: x ?

Smaller0: \(PSPACE\)
Greater0: \(\bigcup_{c>0}SPACE(n^c)\)
Page: 081
Chapter: 4
Section: 1.2
Index: 5
Kind: Def
Smaller to greater: =
Hide middle: yes

Name: NPSPACE
Definition: \(\bigcup_{c>0}NSPACE(n^c)\)
Page: 081
Chapter: 4
Section: 1.2
Index: 4.5
Kind: Def

Definition: \(SPACE(\log n)\)
Page: 081
Chapter: 4
Section: 1.2
Notation: L
Index: 4.5
Kind: Def

Name: NL
Definition: \(NSPACE(\log n)\)
Page: 081
Chapter: 4
Section: 1.2
Index: 4.5
Kind: Def

Smaller0: \(f(n)=o(g(n))\)
Greater0: \[SPACE(f(n))\subsetneq SPACE(g(n))\]
Page: 082
Chapter: 4
Section: 1.3
Index: 8
Kind: Theo
Name: Space hierarchy theorem
Prefix Smaller: \(f,g\) are space-constructible functions satisfying
Suffix Smaller: ,

Name: PSPACE-complete language
Definition: Language both in PSPACE and PSPACE-hard.
Page: 083
Chapter: 4
Section: 2
Index: 9
Kind: Def

Name: A PSPACE-hard language
Definition: A language \(L\) such that \(L\le _p L'\) for every \(L'\in PSPACE\)
Page: 083
Chapter: 4
Section: 2
Index: 9
Kind: Def

Name: A quantified boolean formula
Definition: A formula of the form \(Q_1 x_1\dots Q_n x_n \phi(x_1,\dots,x_n)\) with \(Q_i\) being \(\forall\) or \(\exists\) and \(x_i\) range over \(\{0,1\}\) and \(\phi\) is quantifier free boolean formula.
Page: 083
Chapter: 4
Section: 2
Index: 10
Kind: Def

Name: TQBF
Definition: The set of quantified Boolean formulae that are true.
Page: 084
Chapter: 4
Section: 2
Index: 13
Kind: Def

Name: PSPACE-complete problem
Page: 084
Chapter: 4
Section: 2
Index: 13
Kind: Theo
Example: TQBF.
Extra: Non défini

Smaller0: \(S\) is space-constructible
Greater0: \(\mathbf{NSPACE}(S(n))\subseteq\mathbf{SPACE}(S(n)^2)\)
Page: 086
Chapter: 4
Section: 2.1
Variables: \(S:\mathbb N\to\mathbb N\)
Index: 14
Kind: Theorem
Smaller1: \(S(n)\ge\log n\)
Name: Savitch's Theorem

Name: implicitely \(P\)-space computable function
Definition: there exists \(c\in\mathbb N\) such that \(|f(x)|\le |x|^{c}\). And the problem \(\{\langle x,i\rangle\mid \text{the $i$th bit of $f(x)$ is1}\}\) is computable in space \(P\).
Page: 088
Chapter: 4
Section: 3
Index: 16
Kind: Def
Definition2: the output is written on a write-only tape whose space is not counted in the space limit.
Conjdef: A function \(f\) such that, equivalently

Page: 088
Definition: There exists a function \(f:\{0,1\}^*\to\{0,1\}^*\) that is implicitly logspace computable and such that \(x\in B\) iff \(f(x)\in C\) for every \(x\in\{0,1\}^*\).
Chapter: 4
Section: 3
Variables: \(B,C\subseteq\{0,1\}^*\).
Notation: \(B\le_l C\)
Name: \(B\) is logspace reducible to a language \(C\)
Kind: Def
Index: 16

Name: NL-complete language
Definition: An NL-hard and NL language.
Page: 088, 082
Chapter: 4, 4
Section: 3, 1.2
Variables: \(B\subseteq\{0,1\}^*\).
Index: 16
Kind: Def
Example: PATH

Question: The complement of PATH is in
Answer: NL.
Page: 091
Chapter: 4
Section: 3.2
Index: 20
Kind: Theo

Smaller0: \(S(n)>\log n\)
Greater0: \(=coNSPACE(S(n))\)
Page: 092
Chapter: 4
Section: 3.2
Variables: \(S:\mathbb N\to\mathbb N\).
Index: 21
Kind: Cor
Prefix Greater: \(NSPACE(S(n))\)

Name: Exact Indset
Definition: \(\{\langle G,k\rangle\mid \text{the largest graph independent set in $G$ has size exactly $k$} \} \).
Page: 096
Chapter: 5
Section: 1

Name: MIN-EQ-DNF
Definition: The set of pairs \(\langle \phi,k\rangle\) such that there exists a DNF formula \(\psi\) of size at most \(k\) that is equivalent to the DNF formula \(\phi\).
Page: 096
Chapter: 5
Section: 1

Name: \(\overline{\text{MIN-EQ-DNF} }\)
Definition: \(\{\langle \phi,k\rangle: \forall \text{DNF formula $\psi$ of size $\le k$, $\exists$ an assigment $u$ such that $\phi(u)\ne \psi(u)$}\}\).
Page: 096
Chapter: 5
Section: 1

Definition: The set of languages \(L\) such that there exists a polynomial-time TM \(M\) and a polynomial \(q\) such that \(x\in L\) if and only if \[\exists u_1\in\{0,1\}^{q(|x|)}\forall u_2\in\{0,1\}^{q(|x|)}\dots Q_i u_i\in\{0,1\}^{q(|x|)} M(x,u_1,\dots,u_i)=1.\]
Page: 097
Chapter: 5
Section: 2
Variables: \(i\in\mathbb N^{>0}\)
Notation: \(\Sigma_i^p\)
Index: 3
Kind: Definition

Name: The polynomial hierarchy
Definition: \(\bigcup_i \Sigma_i^p\).
Page: 097
Chapter: 5
Section: 2
Notation: \(\mathbf{ PH}\)
Index: 3
Kind: Definition

Name: Language of \(\Sigma_2^p\)
Page: 097
Chapter: 5
Section: 2
Kind: Ex
Example: EXACT INDSET
Example2: MIN-EQ-DNF

Q: [...] is defined as [...].
A: \(\Pi^p_i\); \(co\Sigma_i^p\)
Page: 097
Chapter: 5
Section: 2

Smaller0: \(\Sigma_i^p=\Sigma_{i+1}^p\)
Greater0: \(PH=\Sigma_i^p\)
Page: 097
Chapter: 5
Section: 2.1
Hide middle: yes
Prefix Greater: that
Name: The polynomial hierarchy collapse
Suffix Smaller: , it

Smaller0: \(\Sigma_i^p=\Pi_i^p\)
Greater0: \(PH=\Sigma_i^p\)
Page: 097
Chapter: 5
Section: 2.1
Variables: \(i\in\mathbb N\)
Index: 4. 1
Kind: Theorem

Smaller0: \(P=NP\)
Greater0: \(P\)
Page: 097
Chapter: 5
Section: 2.1
Index: 4 2
Kind: Theorem
Smaller to greater: iff
Prefix Greater: \(PH=\)

Smaller0: there exists a language \(L\) that is \(PH\)-complete
Greater0: there exists an \(i\) such that \(PH=\Sigma_i^p\)
Page: 098
Chapter: 5
Section: 2.2
Kind: Claim
Extra: plusieurs condition

Smaller0: \(PH\)
Greater0: \( PSPACE\)
Chapter: 5
Section: 2.2
Smaller to greater: \(\subseteq\)
Greater to smaller: \(\supseteq\)

Q: [...] is [...].
A: \(\Sigma_iSAT\); the satisfiability problem restricted to \(i-1\) alternation of quantifiers, beginning by \(\exists\)
Page: 099
Chapter: 5
Section: 2.2
Variables: \(i\in\mathbb N\)
Index: 6
Kind: Ex

Name: An alternating Turing machines
Definition: A Turing machine with two transitions functions, universal and existential states.
Page: 099
Chapter: 5
Section: 3
Index: 7
Kind: Def

Definition: the set of language accepted by a \(T(n)\)-time ATM \(M\) whose initial state is labeled \(\exists\) and on which every input and on every (directed) path from the starting configuration in the configuration graph, \(M\) can alternate at most \(i-1\) times from states with one label to states with the other label.
Page: 100
Chapter: 5
Section: 3
Variables: \(i\in\mathbb N\)
Notation: \(\Sigma_i TIME(T(n))\)
Index: 8
Kind: Definition

Definition: \(\Sigma_i TIME(n^c)\)
Page: 100
Chapter: 5
Section: 3
Variables: \(i\in\mathbb N\)
Notation: \(\Sigma_i^p\)
Index: 9
Kind: Claim

Smaller0: \(AP\)
Greater0: \(PSPACE\)
Page: 100
Chapter: 5
Section: 3.1
Index: 10
Kind: Theorem
Smaller to greater: =
Hide middle: yes

Q: Let [...] be defined as [...].
A: \(AP\); \(\bigcup_c ATIME(n^c)\)
Page: 100
Chapter: 5
Section: 3.1

Definition: the set of languages decided by a TM \(M\) that on every input \(x\) takes at most \(O(T(|x|))\) time and \(O(S(|x|))\) cells of its read-write tapes.
Page: 101
Chapter: 5
Section: 3.1
Variables: \(T,S:\mathbb N\to\mathbb N\).
Notation: TISP\((T(n),S(n))\)
Index: 11
Kind: Theo

Smaller0: \(\Sigma_i^p\)
Greater0: \(\mathbb{NP}^{\Sigma_{i-1}SAT} \)
Page: 102
Chapter: 5
Index: 12
Kind: Theorem
Smaller to greater: =

A language \(L\) such that there exists a polynomial \(p:\mathbb N\to\mathbb N\) and a polynomial-time TM \(M\), called the verifier for \(L\), such that for every \(x\in\{0,1\}^*\),
\[x\in L\iff \exists u\in\{0,1\}^{p(|x|)} \text{ s.t. } M(x,u)=1.\]
If \(x\in L\) and \(u\in\{0,1\}^{p(|x|)}\) satisfy \(M(x,u)=1\) then we call \(u\) a certificate for \(x\) with respect to \(L\) and \(M\).
Page: 039
Chapter: 2, 2
Section: 2, 1
Variables: \(L\subseteq \{0,1\}^*\) a language.
Kind: Def
Name: A non deterministic polynomial time language
Notation: NP language

Name: The configuration graph of \(M\) on \(x\)
Definition: The graph whose nodes are the configurations of the TM and the edges are the transition of the TM, with starting node as the configuration of the initial state.
Page: 080
Chapter: 4
Section: 1.1
Variables: \(M\) a TM
\(X\) a word
Notation: \(G_{M,x}\)

Name: NP-complete problems
Definition: A language which is NP and NP-hard.
Page: 042, 045
Chapter: 2
Section: 3.1
Index: 7, 10
Kind: Def, Theo
Example: SAT, 3SAT
Example2: INDSET
Extra: 2.15-17
Example3: dHAMPATH
Example4: 01 IPROG.

Definition: For an oriented graph \(G\) with \(s\) and \(t\), whether there is a directed graph in which there is a path from \(s\) to \(t\).
Page: 082
Chapter: 4
Section: 1.2
Notation: PATH

Smaller0: \(SAT\)
Greater0: \(TISP(n^{1.1},n^{0.1}) \)
Page: 101
Chapter: 5
Section: 3.1
Index: 11
Kind: Theo
Smaller to greater: \(\not\in\)
Greater to smaller: \(\not\ni\)

Question: There exists a P and NP-hard language
Answer: implies P=NP
Page: 43
Section: 2
Index: 8(2)
Kind: Theo