# The W Hierarchy

50 %
50 %
Education

Published on March 6, 2014

Author: ASPAK2014

Source: slideshare.net

The W-Hierarchy

A Parametereized Problem

A Parametereized Problem NP-hard for constant values of the parameter “Easy” for small values of the parameter

“Easy” for small values of the parameter

“Easy” for small values of the parameter An O(nk) algorithm exists.

“Easy” for small values of the parameter An O(nk) algorithm exists. Fixed-Parameter Tractable: f(k)poly(n) As hard as solving Clique

“Easy” for small values of the parameter An O(nk) algorithm exists. Polynomial “Stuck” with kernel large instances As hard as solving Clique

To establish membership, reduce to X.

A problem is “hard” for a class if every problem in the class reduces to it.

A problem is “hard” for a class if every problem in the class reduces to it.

A problem is “hard” for a class if every problem in the class reduces to it.

A problem is “hard” for a class if every problem in the class reduces to it.

Short Turing Machine Acceptance

Short Turing Machine Acceptance

Short Turing Machine Acceptance

Short Turing Machine Acceptance

Short Turing Machine Acceptance

Short Turing Machine Acceptance

Short Turing Machine Acceptance Input A [ND] Turing machine M, an input x, and an integer k.

Short Turing Machine Acceptance Input A [ND] Turing machine M, an input x, and an integer k. Does M accept x in at most k steps? Question

Independent Set Short Turing Machine Acceptance

Independent Set Short Turing Machine Acceptance (qa,happy)

Independent Set Short Turing Machine Acceptance (qa,happy) Read b and (a,b) is an edge.

Independent Set Short Turing Machine Acceptance (qa,happy) Read b and (a,b) is an edge. (qa,happy) —> (QUIT)

Independent Set Short Turing Machine Acceptance (qa,happy) Read b and (a,b) is not an edge. (qa,happy) —> (QUIT)

Independent Set Short Turing Machine Acceptance (qa,happy) Read b and (a,b) is not an edge. (qa,happy) —> (QUIT) (qa,happy) —> (qa,happy); move right

Independent Set Short Turing Machine Acceptance (qa,happy) (qa,happy) —> (QUIT) (qa,happy) —> (qa,happy); move right

Independent Set Short Turing Machine Acceptance (qa,happy) Read an EOF symbol. (qa,happy) —> (QUIT) (qa,happy) —> (qa,happy); move right

Independent Set Short Turing Machine Acceptance (qa,happy) Read an EOF symbol. (qa,happy) —> (QUIT) (qa,happy) —> (qa,happy); move right (qa,happy) —> (q[move,a],happy); move left

Independent Set Short Turing Machine Acceptance (qa,happy) (qa,happy) —> (QUIT) (qa,happy) —> (qa,happy); move right (qa,happy) —> (q[move,a],happy); move left

Independent Set Short Turing Machine Acceptance (qa,happy) Read a. (qa,happy) —> (QUIT) (qa,happy) —> (qa,happy); move right (qa,happy) —> (q[move,a],happy); move left

Independent Set Short Turing Machine Acceptance (qa,happy) Read a. (qa,happy) —> (QUIT) (qa,happy) —> (qa,happy); move right (qa,happy) —> (q[move,a],happy); move left (q[move,a],happy) —> (q[read],happy); move right

Independent Set Short Turing Machine Acceptance (qa,happy) (qa,happy) —> (QUIT) (qa,happy) —> (qa,happy); move right (qa,happy) —> (q[move,a],happy); move left (q[move,a],happy) —> (q[read],happy); move right

Independent Set Short Turing Machine Acceptance (qa,happy) (qa,happy) —> (QUIT) (qa,happy) —> (qa,happy); move right (qa,happy) —> (q[move,a],happy); move left (q[move,a],happy) —> (q[read],happy); move right (q[read],happy) —> (qb,happy); move right

Dominating Set Short Turing Machine Acceptance

Dominating Set Short Turing Machine Acceptance

Short Turing Machine Acceptance Independent Set

Short Turing Machine Acceptance Independent Set

Short Turing Machine Acceptance Independent Set

Short Turing Machine Acceptance Independent Set

A problem is “hard” for a class if every problem in the class reduces to it.

Short Turing Machine Acceptance

Short Turing Machine Acceptance Encode every configuration as a vertex.

Short Turing Machine Acceptance Encode every configuration as a vertex. At step i, the head is at j, and the transition is δ.

Short Turing Machine Acceptance Encode every configuration as a vertex. At step i, the head is at j, and the transition is δ. At step i, the symbol at j is t, and the head is not at j.

[Step 3, Position 1, δ] [Step 3, Position 2, δ] [Step 3, Position 3, δ]

[Step 3, Position 1, a] [Step 3, Position 1, b] [Step 3, Position 2, a] [Step 3, Position 2, b] [Step 3, Position 3, a] [Step 3, Position 3, b] [Step 3, Position 1, δ] [Step 3, Position 2, δ] [Step 3, Position 3, δ]

[Step 3, Position 1, a] [Step 3, Position 1, b] [Step 3, Position 2, a] [Step 3, Position 2, b] [Step 3, Position 3, a] [Step 3, Position 3, b] [Step 3, Position 1, δ] [Step 3, Position 2, δ] [Step 3, Position 3, δ]

[Step 3, Position 1, a] [Step 3, Position 1, b] [Step 3, Position 2, a] [Step 3, Position 2, b] [Step 3, Position 3, a] [Step 3, Position 3, b] [Step 3, Position 1, δ] [Step 3, Position 2, δ] [Step 3, Position 3, δ]

[Step 3, Position 1, a] [Step 3, Position 1, b] [Step 3, Position 2, a] [Step 3, Position 2, b] [Step 3, Position 3, a] [Step 3, Position 3, b] [Step 3, Position 1, δ] [Step 3, Position 2, δ] [Step 3, Position 3, δ]

[Step 3, Position 1, a] [Step 3, Position 1, b] [Step 3, Position 2, a] [Step 3, Position 2, b] [Step 3, Position 3, a] [Step 3, Position 3, b] [Step 3, Position 1, δ] [Step 3, Position 2, δ] [Step 3, Position 3, δ]

Introducing… CIRCUITS

CIRCUITS

CIRCUITS

Weighted Circuit Satisfiablity

Weighted Circuit Satisfiablity Input A circuit C, and an integer k.

Weighted Circuit Satisfiablity Input A circuit C, and an integer k. Is there an assignment setting EXACTLY k variables to one, that satisfies C? Question

Independent Set Weighted Circuit Satisfiability e b c a t d h f g

Independent Set Weighted Circuit Satisfiability e b c a t d t h f g h

Independent Set Weighted Circuit Satisfiability e b c a t d t h f g h AND

Independent Set Weighted Circuit Satisfiability e b c a t d t h f g h AND

Independent Set Weighted Circuit Satisfiability e a t t h NOT b c d h f g AND

Independent Set Weighted Circuit Satisfiability

Independent Set Weighted Circuit Satisfiability

Independent Set Weighted Circuit Satisfiability

Independent Set Weighted Circuit Satisfiability

Independent Set Weighted Circuit Satisfiability Vertices as Input Gates NOT Gates Edges as AND Gates Output Gate [AND]

Dominating Set Weighted Circuit Satisfiability

Dominating Set Weighted Circuit Satisfiability OR Gates

Dominating Set Weighted Circuit Satisfiability OR Gates AND Gate

Dominating Set Weighted Circuit Satisfiability OR Gates AND Gate

Dominating Set Weighted Circuit Satisfiability OR Gates AND Gate

Dominating Set Weighted Circuit Satisfiability OR Gates AND Gate Set a Dominating Set to 1 and the rest to 0…

Dominating Set Weighted Circuit Satisfiability OR Gates AND Gate Set a Dominating Set to 1 and the rest to 0…

Dominating Set Weighted Circuit Satisfiability OR Gates AND Gate Otherwise:

Weighted Circuit Satisfiability Independent Set

Weighted Circuit Satisfiability Independent Set

Weighted Circuit Satisfiability Independent Set

Weighted Circuit Satisfiability Independent Set

The weft of a circuit is the maximum number of large nodes on a path from an input node to the output node. *Nodes with in-degree more than two.

Independent Set Weighted Circuit Satisfiability Vertices as Input Gates NOT Gates Edges as AND Gates Output Gate [AND]

Dominating Set Weighted Circuit Satisfiability OR Gates AND Gate

Weighted Circuit Satisfiability restricted to circuits of weft 1. Independent Set, Clique, etc. W[1]

Weighted Circuit Satisfiability restricted to circuits of weft 2. W[2]

Weighted Circuit Satisfiability restricted to circuits of weft 2. Dominating Set, Set Cover, Hitting Set W[2]

Weighted Circuit Satisfiability restricted to circuits of weft 2. Dominating Set, Set Cover, Hitting Set W[2]

Weighted Circuit Satisfiability restricted to circuits of weft 2. Dominating Set, Set Cover, Hitting Set W[2]

CIRCUITS & SATISFIABILITY (as we know it)

Independent Set Weighted Circuit Satisfiability Vertices as Input Gates NOT Gates Edges as AND Gates Output Gate [AND]

Input Gates NOT Gates AND Gates Output Gate [AND]

(x y) (z x) ··· (z y) Input Gates NOT Gates AND Gates Output Gate [AND]

Dominating Set Weighted Circuit Satisfiability OR Gates AND Gate

OR Gates AND Gate

(x y a b p q) (z OR Gates AND Gate x r) ··· (z y p q z)

Weighted Circuit Satisfiability restricted to circuits of weft 2.

Weighted Circuit Satisfiability restricted to circuits of weft 2. Weighted SAT for Appropriately Normalized & Monotone Formulas

Weighted Circuit Satisfiability restricted to circuits of weft 2. Weighted SAT for Appropriately Normalized & Monotone Formulas

Weighted Circuit Satisfiability restricted to circuits of weft 2. Weighted SAT for Appropriately Normalized & Monotone Formulas

Weighted Circuit Satisfiability restricted to circuits of weft 2. Weighted SAT for Appropriately Normalized & Monotone Formulas Dominating Set, Set Cover, Hitting Set

Weighted Circuit Satisfiability restricted to circuits of weft 2. Weighted SAT for Appropriately Normalized & Monotone Formulas Dominating Set, Set Cover, Hitting Set

Weighted Circuit Satisfiability restricted to circuits of weft 2. Weighted SAT for Appropriately Normalized & Monotone Formulas Dominating Set, Set Cover, Hitting Set

Weighted Circuit Satisfiability restricted to circuits of weft 2. Weighted SAT for Appropriately Normalized & Monotone Formulas Dominating Set, Set Cover, Hitting Set

(x y a b p q) (z x r) ··· (z y p q z)

(x y a b p q) (z x r) ··· (z y p q z)

(x y a b p q) (z p x r) ··· (z y p q z)

(x y a b p q) (z p x r) ··· (z y p q z)

 User name: Comment:

## Related presentations

#### Top 3 Anti Plagiarism Software In India For Univer...

September 25, 2020

#### Things to know about Arthroscopy | Dr. Ketas Mahaj...

September 26, 2020

#### Top 10 best international schools in Singapore

September 26, 2020

#### Latest Questions Answers for SAP BI C_TB1200_93 Ce...

September 26, 2020

#### [2020] 10 Actionable Tips to Ace Your Oracle 1Z0-4...

September 26, 2020

#### Davao medical college fees structure

September 26, 2020

## Related pages

### The W-Hierarchy | springerprofessional.de

We introduce the W-hierarchy of parameterized complexity classes in the tower

### dict.cc Wörterbuch :: hierarchy :: Deutsch-Englisch ...

Englisch-Deutsch-Übersetzung für hierarchy im Online-Wörterbuch dict.cc (Deutschwörterbuch).

### The WordPress Template Hierarchy - a visualization resource

The WordPress Template Hierarchy . Menu WP Hierarchy. is current up to: WordPress 4.6. Latest update: Tuesday June 28, 2016: Udpate stripCount and adjust ...

### Hierarchy | Definition of Hierarchy by Merriam-Webster

The church hierarchy faced resistance to some of their decisions. He was at the bottom of the corporate hierarchy. a rigid hierarchy of social classes.

### The W-Hierarchy - Springer

Based on the syntactic approach to complexity theory laid out in Chap. 4, we introduced the classes W ( [1] ), W ( [2],dots ), of the W-hierarchy by ...

### dict.cc | hierarchy | Wörterbuch Englisch-Deutsch

Übersetzung für hierarchy im Englisch-Deutsch-Wörterbuch dict.cc.

### Descriptive Complexity and the W Hierarchy - researchgate.net

DESCRIPTIVE COMPLEXITY AND THE W HIERARCHY 3 For the completeness notion, Downey and Fellows [DF95] de ned a hierarchy of classes of parameterized languages

### An analysis of the W*-hierarchy - Semantic Scholar

An analysis of the W*-hierarchy. Yijia Chen, Jörg Flum, Martin Grohe; JSYML; 2007; View PDF; Cite; Save; Abstract. We observe that the W *-hierarchy, a ...