Title: Theory / Unimportant / CS / Algo / Approximation / Vazirani +18{ / A Complexity
Tags: récupéré
On every note of this deck, unless a note says otherwise:
Chapter: A

Name: A decision problem
Definition: A problem whose answer is either yes or no
Page: 343
Section: 1
Example: sat
Example2: cardinality vertex cover

Name: SAT
Definition: Given a Boolean formula in conjunctive normal form, f , is there is a satisfying truth assignment for f ?
Page: 343
Section: 1

Name: Cardinality vertex cover
Definition: Given an undirected graph \(G\) and integer \(k\), does \(G\) have a vertex cover of size \(\le k\)?
Page: 343
Section: 1

Name: kSAT
Definition: the restriction of SAT to instances in which each clause contains at most k literals
Page: 343
Section: 1

Name: A language
Definition: A subset of \(\{0,1\}^*\)
Page: 343
Section: 1

Name: A language associated to \(\Pi\)
Definition: The set of binary encoding of the "yes" instances of the decision problem
Page: 343, 344
Section: 1
Variables: \(\Pi\) a decision problem

Definition: The set of language whose complement belong to NP
Page: 344
Section: 1
Notation: coNP
Applied to3: set of short, quickly verifiable No certificates

Name: Non deterministic, Polynomial
Definition: The set of language such that there exists a verifier for this language, time bounded by a polynomial
Page: 343
Section: 1
Abbreviation: NP
Applied to3: set of short, quickly verifiable yes certificates

Name: A verifier for \(L\)
Definition: for each string \(x\in\{0,1\}^*\), (there is a string \(y\) of polynomial length such that \(M(x,y)\) accepts) iff \(x\in L\)
Page: 343
Section: 1
Variables: \(L\) a language

Name: A certificate for \(x\)
Definition: a string \(y\) of polynomial length such that \(M(x,y)\) accepts
Page: 344
Section: 1
Variables: \(L\) a language
\(M\) a verifier
\(x\in\{0,1\}^*\)
Name2: A proof for \(x\)
Example2: A witness for \(x\)
Intuition: A solution for \(x\)

Name: Polynomial time reduction
Definition: The relation on languages \(L_1,L_2\) such that there is a polynomial time Turing machine \(T\) which given a string \(x\in \{0,1\}^*\), outputs string \(y\) such that \(x\in L_1\iff y\in L_2\)
Page: 344
Section: 2
Context: TM
Notation: \(\preceq\)
Typ: transitive

Definition: every \(L'\in\mathbf{NP}\), \(L'\preceq L\),
Page: 344
Section: 2
Notation: NP-hard
Definition2: some NP-complete language \(L'\) is such that \(L'\preceq L\).
Conjdef: The set of languages, such that, equivalently

Name: Combinatorial optimization problem
Definition: A problem consisting in picking the “best” solution from a finite set.
Page: 345
Section: 3

Name: The set of valid instances
Page: 345
Section: 3
Variables: \(\Pi\) a NP-optimization problem
Notation: \(D_\Pi\)
Typ: Recognizable in polynomial time

Name: The size of \(I\)
Definition: the number of bits needed to write \(I\) under the assumption that all numbers occurring in the instance are written in binary.
Page: 345
Section: 3
Variables: \(\Pi\) a NP-optimization problem
\(I\) an instance
Notation: [$]\abs{I}[/$]

Name: The set of feasible solutions of \(I\)
Definition: non-empty
Page: 345
Section: 3
Variables: \(\Pi\) a NP-optimization problem
\(I\) an instance
Notation: \(S_\Pi(I)\)
Definition2: of length polynomially bounded in [$]\abs{I}[/$]
Conjdef: A set
Definition3: such that, given \((I,s)\), it is decidable in P whether \(s\in S_\Pi(I)\)

Name: An objective function for \(\Pi\)
Definition: in P
Page: 346
Section: 3
Variables: \(\Pi\) a NP-optimization problem
\(I\) an instance
Notation: \(\mathrm{obj}_\Pi\)
Definition2: from instance and solutions to non-negative rationals
Conjdef: A function
Applied to3: cost, length, weight

Name: A NP-optimization problem
Definition: A set of valid instances \(D_\Pi\)
Page: 346
Section: 3
Notation: \(\Pi\)
Definition2: for each instance, a set of feasible solutions \(S_\Pi(I)\)
Conjdef: A tuple with
Definition3: an objective function \(\mathrm{obj}_\pi\)
Definition4: whether it is a minimization or a maximization problem

Name: The cardinality version of \(\Pi\)
Definition: A version of \(\Pi\) with the objective function being the constant 1
Page: 346
Section: 3
Variables: \(\Pi\) a NP-optimization problem

Name: An optimal solution
Definition: A feasible solution that achieves the smallest or largest objective function value.
Page: 346
Section: 3
Variables: \(\Pi\) a NP-optimization problem
\(I\) an instance

Name: the objective function value of an optimal solution to instance \(I\)
Page: 346
Section: 3
Variables: \(\Pi\) a NP-optimization problem
\(I\) an instance
Notation: \(\mathrm{OPT}_\Pi(I)\)
Denoted by: \(\mathrm{OPT}\) when \(\Pi\) is clear

Name: The decision version of \(\Pi\)
Definition: The problem, taking as input an instance \(I\) and a rational \(B\), of deciding whether there is a solution with cost at least/most \(B\)
Page: 346
Section: 3
Variables: \(\Pi\) a NP-optimization problem

Name: A NP-hard optimization problem
Definition: An optimization problem whose decision problem is NP-hard.
Page: 346
Section: 3

Name: An approximation algorithm
Definition: An algorithm which produces a feasible solution that is “close” to the optimal one, and is time efficient.
Page: 346
Section: 3

Name: A factor \(\delta\) randomized approximation algorithm for \(\Pi\)
Definition: on each instance \(I\), \(\mathcal A\) produces a feasible solution \(s\) for \(I\)
Page: 346
Section: 3
Variables: \(\Pi\) an optimization problem
\(\delta:\mathbb Z^+\to\mathbb Q^+\),
Definition2: such that there is at least 1/2 probability that \(f_\Pi(I,s)\) is at least (resp. at most) \(\delta(|I|)\mathrm{OPT}(I)\)
Conjdef: A randomized algorithm \(\mathcal A\) such that
Definition3: the running time is bounded by a fixed polynomial in [$]\abs{I}[/$]
Assuming: \(\delta\ge1\) (resp, \(\delta\le 1\))
Applied to2: Mathjax  (resp,  Mathjax )

Name: A factor \(\delta\) approximation algorithm for \(\Pi\)
Definition: on each instance \(I\), \(\mathcal A\) produces a feasible solution \(s\) for \(I\)
Page: 346
Section: 3
Variables: \(\Pi\) an optimization problem
\(\delta:\mathbb Z^+\to\mathbb Q^+\),
Definition2: such that \(f_\Pi(I,s)\) is at least (resp. at most) [$]\delta(\abs{I})\cdot\mathrm{OPT}(I)[/$] and
Conjdef: An algorithm \(\mathcal A\) such that
Definition3: the running time is bounded by a fixed polynomial in [$]\abs{I}[/$]
Assuming: \(\delta\ge1\) (resp, \(\delta\le 1\))