Title: Theory / Unimportant / CS / Fundamental / Complexity / Parametrized / Downey, Fellows{ / 1 Intro
Tags: récupéré MissingMedia

Name: Vertex cover problem
Definition: The problem which, given a graph \(G\) and an integer \(k\), state whether there is a set of vertices of size \(k\) that is a vertex cover
Page: xiv
Chapter: intro

Name: Independent set problem
Definition: The problem which, given a graph \(G\) and an integer \(k\), state whether there is a set of vertices of size \(k\) that is an independent set
Page: xiv
Chapter: intro

Name: Dominating set problem
Definition: The problem which, given a graph \(G\) and an integer \(k\), state whether there is a set of vertices of size \(k\) that is an dominating set
Page: xiv
Chapter: intro

Name: Dominating set
Definition: A set of vertices \(V'\) such that every vertex in \(G\) has at least one neighbour in \(V'\).
Page: xiv
Chapter: intro
Variables: \(G\) a variable

Name: Independent set
Definition: A set of vertices \(V'\) such that no two of them are neighbors
Page: xiv
Chapter: intro
Variables: \(G\) a variable

Name: Vertex cover
Definition: A set of vertices \(V'\) such that every edge as at least an endpoint in \(V'\).
Page: xiv
Chapter: intro
Variables: \(G\) a variable

Name: Unary alphabet
Definition: \(\{1\}\)
Page: 3
Chapter: 1

Name: Binary alphabet
Definition: \(\{0,1\}\)
Page: 3
Chapter: 1
Notation: \(\Sigma\)

Definition: The set of finite words over alphabet \(\Sigma\)
Page: 3
Chapter: 1
Variables: \(\Sigma\) an alphabet
Notation: \(\Sigma^*\)

Name: Basic complexity definitions are
Definition: omitted
Page: 3
Chapter: 1

Name: many-one polynomial time reductibility
Page: 4
Chapter: 1
Notation: \(\le_m^P\)

Name: polynomial-time Turing reductibility
Definition: Reduction using an oracle for the language to which the reduction goes
Page: 4
Chapter: 1
Notation: \(\le_m^T\)
Name2: polynomial-time Cook reductibility

Smaller0: PH
Greater0: PSpace
Page: 6
Chapter: 1
Smaller to greater: \(\subseteq\)
Greater to smaller: \(\supseteq\)

Name: Quantified Boolean Formula Sat
Definition: Given a quantified boolean formula, is it satisfiable ?
Page: 6
Chapter: 1
Abbreviation: QBFSat

Question: Complexity of QBFSat
Answer: PSpace-complete
Page: 6
Chapter: 1

Name: An advice function
Definition: A function \(f:\Sigma^*\to\Sigma^*\) such that [$]\abs{x}=\abs{y}[/$] implies \(f(x)=f(y)\).
Page: 7
Chapter: 1
Section: 2

Name: A polynomial advice function
Definition: An advice function \(f\) such that [$]\abs{f(n)}<n^c[/$] for some constant \(c\)
Page: 7
Chapter: 1
Section: 2

Definition: The class of language, accepted by TM of class \(\mathcal C\), whose input is \(\langle x,f(x)\rangle\) for some polynomial advice function \(f\)
Page: 7
Chapter: 1
Section: 2
Variables: \(\mathcal C\) a complexity class
Notation: \(\mathcal C/\mathrm{Poly}\)

Smaller0: P/Poly
Greater0: NC
Page: 8
Chapter: 1
Section: 2
Smaller to greater: =

Smaller0: \(\Pi_i^p\subseteq\Sigma_i^p/Poly\) and \(\Sigma_i^p\subseteq\Pi_i^p/Poly\)
Greater0: \(PH=\Sigma_i^p/Poly=\Pi_i^p/Poly\)
Page: 8
Chapter: 1
Section: 2
Index: 1, 2
Kind: Lem, Cor
Smaller to greater: iff

Smaller0: \(\Sigma_i^p\subseteq\Pi_i^p/Poly\)
Greater0: \(\Sigma_{i+2}^p=PH\)
Page: 8
Chapter: 1
Section: 2
Kind: Lem

Name: A RP turing machine
Definition: A NDTM such that each word is either not accepted, or accepted by at least 3/4 of the computations
Page: 8
Chapter: 1
Section: 3
Kind: Def

Name: The language accepted by \(M\) as a RP Turing Machine
Definition: the language accepted by \(M\) as a NDTM
Page: 8
Chapter: 1
Section: 3
Variables: \(M\) a RP turing machine
Kind: Def

Name: The language accepted by \(M\) as a BPP Turing Machine
Definition: the language accepted by at least 3/4 of the computation of \(M\) as a NDTM
Page: 8
Chapter: 1
Section: 3
Variables: \(M\) a BPP turing machine
Kind: Def

Name: A BPP turing machine
Definition: A TM such that each word is either accepted or rejected by at least 3/4 of the path
Page: 8
Chapter: 1
Section: 3
Kind: Def

Name: Probability amplification
Definition: Repeating a randomized run \(n^{c+d}\) times, so that the result TM accepts/rejects with probabilyt \(1-2^{-n^d}\)
Page: 10
Chapter: 1
Section: 3
Context: TM
Kind: Def

Smaller0: BPP
Greater0: \(\Sigma_2^P\cap\Pi_2^P\)
Page: 10
Chapter: 1
Section: 3
Kind: Theo
Smaller to greater: is included in
Greater to smaller: contains
Context: TM

Smaller0: NP
Greater0: \(\mathrm{RP^{USAT}}\)
Page: 10
Chapter: 1
Section: 3
Kind: Theo
Smaller to greater: is included in
Greater to smaller: contains

Name: Unique Satifsiability
Definition: The problem, taking as input a CNF, returning whether there exists a unique assignment satisfying this formula.
Page: 10
Chapter: 1
Section: 3
Abbreviation: USat

Name: parameterized language
Definition: subset of \(\Sigma^*\times\Sigma^*\)
Page: 15
Chapter: 2
Section: 1

Name: parameterized word
Page: 15
Chapter: 2
Section: 1
Variables: \(L\) a parameterized language
Notation: \(\langle x,k\rangle\)

Name: the parameter of this word
Definition: \(k\)
Page: 15
Chapter: 2
Section: 1
Variables: \(L\) a parameterized language
\(\langle x,k\rangle\) a parameterized word

Name: The \(k\)-th slice of \(L\)
Definition: the set of \(x\) such that \(\langle x,k\rangle\in L\)
Page: 15
Chapter: 2
Section: 1
Variables: \(L\) a parameterized language
\(k\) a parameter
Notation: \(L_k\)

Name: A parametrized language tractable by the slice
Definition: A parameterized language such that there is a constant \(c\) such that each \(L_k\) is determined in time [$]O(\abs{x}^c)[/$]
Page: 15
Chapter: 2
Section: 1

Name: Fixed-parameter tractable
Definition: there exists an algorithm \(\Phi\)
Page: 15
Chapter: 2
Section: 1
Definition2: there exists a constant \(c\)
Conjdef: A parameterized language such that
Definition3: there exists a computable function \(f\)
Abbreviation: FTP
Definition4: such that for all \(x,k\), \(\Phi(\langle,x,k\rangle)\) runs in time at most [$]f(k)\abs{x}^c[/$] and
Definition5: \(\langle x,k\rangle\in L\) iff \(\Phi(\langle,x,k\rangle)=1\)